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.
Context free grammar for $bin(n)bin(n+1)^R$
formal languages;context free;formal grammars;pushdown automata
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$.