How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?

Question

This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3.

$$ \text {Let }b_i \text{ denote } i \text{ in binary without leading zeros.}$$ We need to construct a CFG which generates the following language: $$ \{0, 1, 2\}⁺ - \{b_12b_22...2b_n | \text{n is a whole number}\} \text{.} $$

Firstly, I considered implementing such non-terminal $$ U \mid \forall \text{whole n}. S \Rightarrow^+ U \Rightarrow^+ b_12b_22...2b_n\text{.} $$ I believe that even if this could be done, it would have a fairly cumbersome structure: $$ \{b_12b_22...2b_n | \text{n is a whole number}\} $$ does not satisfy the Pumping lemma, therefore, is not a CFL. For the same reason, I can't see any way to apply any neat theorems like $$CFL - RL = CFL\text{.}$$

How could one construct such a grammar? I would really appreciate some hints, which could help me solve the problem, instead of a complete solution.

Answer 1

Here is the idea. We can always write the string in the form $w_1\#\cdots\#w_n$, for some strings $w_i \in \{0,1\}^*$. If the input string is not of the form $b_1\#\cdots\#b_n$, then one of the following must happen:

• $w_1 \neq 1$.
• One of the $w_i$'s is empty.
• One of the $w_i$'s has a leading $0$.
• For some $i$, $w_i+1 \neq w_{i+1}$.

The first three cases are easy. In the first case, the string is empty or starts with $\#,0,10,11$. In the second case, there is a substring $\#\#$. In the third case, there is a substring $\#0$.

For the fourth case, let $x = w_i$ and $y = w_{i+1}$. Here are some things which are not supposed to happen:

• $x$ ends with $1^m$ and $y$ ends with $10^{m-1}$.
• $x$ ends with $01^m$ and $y$ ends with $0^{m+1}$.
• $x = 1^m$ and $y = 0^m$. (Actually this is ruled out by requiring no leading zeroes.)
• $x$ starts $\{0,1\}^ib\{0,1\}^*0$ and $y$ starts $\{0,1\}^i \overline{b}$.

Unless I missed some case, if none of these things happen, then $y$ is the encoding of $x+1$. Indeed, the first two constraints guarantee that if $x=z01^m$ then $y=w10^m$ (the third constraint takes care of the corner case $x=1^m$, in which case $y=10^m$), and the fourth constraint guarantees that $z=w$.

Each of these subcases corresponds to a context-free language – once again, there are some corner cases to consider (if $x = w_1$ and if $y = w_n$).