# 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?

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.

• – f9c69e9781fa194211448473495534 Apr 2 at 13:12
• @f9c69e9781fa194211448473495534 should I close down my other attempts? I'm sorry for the inconvenience. – Zhiltsoff Igor Apr 2 at 13:51
• Yes, that would be a good idea. – Yuval Filmus Apr 2 at 14:06
• I primarily wanted to prevent people from taking the time to answer your question twice. – f9c69e9781fa194211448473495534 Apr 2 at 15:28

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$$).