Question

There is a result for context-free languages analogous to the pumping lemma for regular sets. Suppose that \(L(G)\) is the language recognized by a context-free language \(G\). This result states that there is a constant N such that if z is a word in \(L(G)\) with \(l(z) \ge N\), then z can be written as u v w x y, where \(l(vwx) \le N,l(vx) \ge 1\), and \({\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}}{{\bf{x}}^{\bf{i}}}{\bf{y}}\) belongs to \(L(G)\) for \({\bf{i = 0,1,2, \ldots }}\).Use this result to show that there is no context-free grammar \(G\) with \(L(G) = \left\{ {{0^n}{1^n}{2^n}\mid n = 0,1,2, \ldots } \right\}\).

Short answer

By using a proof by contradiction, it shown that there is no exist a context-free grammar \(G\) with \(L{\rm{(}}G{\rm{)}} = \left\{ {{0^n}{1^n}{2^n}\mid n = 0,1,2, \ldots } \right\}\).

Step-by-step solution

Definition

Pumping lemma: If \(x\) is a string in \(L{\rm{(}}M{\rm{)}}\) with \(L{\rm{(}}x{\rm{)}} \ge |S|\), then there are strings \(u,v\) and \(w\) in \({I^*}\) such that \(x = uvw,{\bf{ }}L{\rm{(}}uv{\rm{)}} \le |S|\) and \(l{\rm{(}}v{\rm{)}} \ge 1\) and \(u{v^i}w \in L{\rm{(}}M{\rm{)}}\) for \(i = 0,1,2, \ldots \)

Proving by contradiction

Given:

language recognized by context-free grammar \(G\)

There exists a constant \(N\) such that if \(z\) is a word in \(L{\rm{(}}G{\rm{)}}\) with \(l{\rm{(}}w{\rm{)}} \ge N,l{\rm{(}}vwz{\rm{)}} \le N\) and \(l{\rm{(}}vx{\rm{)}} \ge 1\), then \(z = u{v^i}w{x^i}y\) belongs to \(L{\rm{(}}G{\rm{)}}\) for \(i = 1,2,3, \ldots \)

To proof: There does not exist a context-free grammar \(G\) with \(L{\rm{(}}G{\rm{)}} = \left\{ {{0^n}{1^n}{2^n}\mid n = 0,1,2, \ldots } \right\}\)

Proof by contradiction:

Assume, for the sake of contradiction, that there exists a context-free grammar \(G\) with \(L{\rm{(}}G{\rm{)}} = \left\{ {{0^n}{1^n}{2^n}\mid n = 0,1,2, \ldots } \right\}\)

Using the pumping lemma

By the pumping lemma, there exists an integer \(N\) such that \({0^N}{1^N}{2^N} = uvwxy\). with \(l{\rm{(}}w{\rm{)}} \ge N,l{\rm{(}}vwx{\rm{)}} \le N\) and \(l{\rm{(}}vx{\rm{)}} \ge 1\).

If \(v\) and \(w\) contain two or three different symbols, then the order of the \(0's\), \(1's\) and \(2's\) will no longer be of the form \({0^n}{1^n}{2^n}\) in \(u{v^2}w{x^2}y\) and thus this is not possible. Thus \(v\) and \(w\) need to contain a sequence of one symbol each

If \(v\) and \(w\) both contain a sequence of \(1\) symbol each, then \(u{v^2}w{x^2}y\) will contain one symbol less (for example, if \(v\) contains \(0's\) and \(w\) contains \(1's\), then \(u{v^2}w{x^2}y\) contains less \(2's\) than \(0's\) and \(1's\)). Thus, you then obtained a contradiction.

Therefore, our assumption " \(G\) exists" is incorrect and thus such a context-free grammar \(G\) does not exist.