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

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.

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*}
• $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$.
• Thanks for your answer. Do you know meybe grammar for $L = \{bin(n)bin(n+1) : n \geq 0\}$ ? It's same, but without reversing $bin(n+1)$ – maqo May 27 '17 at 12:26
• It's a very standard exercise. You can also try reducing to the language $a^nb^mc^nd^m$. – Yuval Filmus May 27 '17 at 13:35