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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.