Context Free Grammar for Unary Addition

Question

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.

Answer 1

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

Answer 2

S => 1A1
A => 1A1 | +1B1
B => 1B1 | =

The first two rows construct the first term and the sum with the same number of ones. Once the first term is constructed, you move onto the second with "A => +1B1." The third row constructs the second term, simultaneously adding an equal number of ones to the sum. Once you're done, the equals transition finishes it up.

Note that this doesn't allow any term in the expression to equal zero. Also, you can construct unary minus expressions with a slight variation, keeping in mind that a - b = c is equivalent to a = b + c

Answer 3

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.

Answer 4

Generic unary addition not possible with a context free grammar or with a pushdown automaton. For this type of computation you must use a Turing Machine. Writing a pushdown automaton that pushes 1's onto the stack is not valid because the stack is not really the output of a PDA. The only output of a PDA is a binary "Accept" or "Reject" which indicates whether or not the input string is a part of the language that is recognized by the PDA.

Answer 5

Yeah, this one has been bothering me for the past hour.

Also, cdiggins, 1 + 1 = 111 would pass that

Answer 6

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?

Answer 7

S   ->  1 + 1 = 11
S   ->  1S1
S   ->  1 + 1A11
A   ->  1 = 1
A   ->  1A1

Answer 8

I know its an old question, I was reading Godel, Escher, Bach and was struck on similar problem (of generating a grammer for its pq system)

So for the OP's question, I guess the following production rules should do:

first -> 1+second1 | 1first1 second -> 1=1 | 1second1