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

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 2

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.