Let b(n) denote the binary representation of n >= 1, leading zeros omitted. For example, b(5) = 101 and b(12) = 1100. Let $ be another symbol not in {0,1}.
Suppose we reverse the first numeral; that is, consider the set
{revb(n)$b(n+1) | n >= 1}. Show that this set is a CFL.
Does someone know how to obtain the grammar for this language? Thanks
Observe the following. For the moment, we allow leading zeros in binary representations. Then, for a given $n \geq 1,$ its binary representation has the form $*\cdots*01\cdots1,$ where the $*$'s are arbitrary digits (there may be none), then we have one zero (maybe leading), and finally we have a sequence of $k$ $1$'s with $k\geq 0,$ in particular $k=0$ is allowed. The important thing is that from this binary representation of $n,$ we get that the binary representation of $n+1$ is $*\cdots*10\cdots0,$ where the $*$'s are the same as for $n,$ then we have a $1$, and finally we have $k$ zeros. This is true because if we add $1$ to $n,$ then in the binary representation all the trailing $1$'s are flipped to $0,$ then the $0$ is flipped to $1,$ and all the $*$'s are unchanged.
From this description of binary addition we can construct the following context free grammar. Variables are lowercase letters, terminals are 0, 1, $. The root variable is z.
z = y | x
y = 1\$10 | 1 y 0
x = 1 x 0 | 0 w 1
w = 1\$1 | 1 w 1 | 0 w 0
The production for y handles the case that b(n) is a string of $1$'s. The productions for x and w handle the case that b(n) contains $0$'s and $1$'s and has a leading $1.$
