Given an alphabet of 1s I want to parse addition of the form
1^k + 1^j = 1^k+j
This is pretty easy to represent with a pushdown automaton simply by pushing a 1 on to the stack on each of the first two 1s, and then popping on the last set of 1s. However, I can't seem to figure out how to represent this as a context free grammar, which is obviously possible since PDA == CFG.
My advice is to make a simple starting point: 1+1=11 And now try to figure out how you can "grow" that with legal CFG expressions.
Alternatively, I solved this just now by trying to extend it with "matching parenthesis", which is a common introduction problem to CFGs. Its obviously harder, but you may find a fruitful path that way.
Hope this helps! Happy hunting.
Agor
If you rewrite the RHS as 1^j1^k, then you should see it's just two nested sets of balanced 1s. Combined with a "base case" of 1 + 1 = 11, you should be able to grow the "j"s on the inside and the "k"s on the outside.
Yeah, this one has been bothering me for the past hour.
Also, cdiggins, 1 + 1 = 111 would pass that
i have been workin on this forever also and cant get it to work. this is what makes most sense to me:
A -> B + B = BB B -> BB B -> 1
but yea, this accepts strings like 1 + 111 = 11 and 11 + 1 = 111111 and other nonsense. seems like people here know but don't feel like sharing. this isnt exactly something we can google and get meaningful help. think you could be slightly more helpful?