Prove that the following context-free grammar does not generate the language by finding a word of the language that is not generated by the grammar.

Question

Here is the language:

$\{w \in $ {$0,1$}$^* \mid w$ has 2 to 3 times more $0$ than $1$, inclusively$\}$

The following grammar does not generate such language. Prove it by finding a word of the language that is not generated by the grammar.

$S \rightarrow\varepsilon $

$| 001S | 00S1 | 0S01 | S001 $

$| 010S | 01S0 | 0S10 | S010 $

$| 100S | 10S0 | 1S00 | S100 $

$| 0001S | 000S1 | 00S01 | 0S001 | S0001 $

$| 0010S | 001S0 | 00S10 | 0S010 | S0010 $

$| 0100S | 010S0 | 01S00 | 0S100 | S0100 $

$| 1000S| 100S0| 10S00| 1S000|S1000 $

The grammar clearly always respects the condition that there is always 2 to 3 times more $0$ than $1$, inclusively.

In every case, there is either 2 "$0$" and 1 "$1$" OR 3 "$0$" and 1 "$1$".

So for 100 "$1$", I can have 200 to 300 "$0$", which is what we want.

I can have words starting with only "$1$"s and ending with "$0$" with $|1S000|$ and $|1S00|$. The reverse can be done with $|000S1|$ and $|00S1|$.

The other cases can be used to alternate "$1$"s and "$0$"s in the word.

So I really can't think of a word in the language that the grammar can't generate!

Any help appreciated!

Answer 1

This grammar is incapable of generating any word that both starts and ends with 0000. Pick any word of the language that satisfies this constraint: there are plenty to choose from of many different lengths.

Answer 2

Any substitution adds $3$ or $4$ terminals to the string, so if a string generated by the grammar is $16$ characters long, it must be formed by substituting $4$ of the last $20$ strings, since the only solution of $3s+4t=16$ in nonnegative integers is $(s,t)=(0,4)$ Thus, any such string will contain exactly $4$ ones. Thus, any $16-$bit string with exactly $5$ ones is a string in the language that cannot be generated by the grammar.