Context free grammar for $bin(n)bin(n+1)^R$

Question

It is pretty hard for me to understand, how binary representation of number may be context free. This language $L=\{bin(n)bin(n+1)^R : n \geq 0\}$ is context free.

Here, at 1.b, is a PDA which describes this language, so it is context free. I've tried to construct a context free grammar for this one, but I have no idea when to even start. How can I express a CFG binary representation of a number? I would be very glad for any suggestions.

Answer 1

Here is one solution: $$ \begin{align*} &S \to 01 \mid 1A1 \mid 1B1 \\ &A \to 1A0 \mid 0 \\ &B \to 1B1 \mid 0B0 \mid 0C1 \\ &C \to 1C0 \mid \epsilon \end{align*} $$

Explanation:

• $A$ generates $1^n 0^{n+1}$, and so $1A1$ generates $1^{n+1} 0^{n+1}1$, which handles numbers whose binary expansion is $1^{n+1}$.
• $C$ generates $1^n 0^n$, and so $0C1$ generates $01^n 0^n1$.
• $B$ generates $w01^n0^n1w^R$, and so $1B1$ generates $1w01^n0^n1w^R1$, which handles numbers whose binary expansion is $1w01^n$.
• Finally, $01$ handles $0$.