Proof of Pumping Lemma for CFL

Re: Proof of Pumping Lemma for CFL

by Giorgio Satta -
Number of replies: 0

The pumping lemma proof factorises a complete parse tree for string \(z\) into three parts. If we look at this from the perspective of derivations, we can write the factorisation as consisting of the three separate derivations \( S \Rightarrow^\ast uAy \), \( A \Rightarrow^\ast vAx \), and \( A \Rightarrow^\ast w \).

To explain the condition \( vx \neq \varepsilon \) in the pumping lemma, focus on the subserivation \( A \Rightarrow^\ast vAx \). We know that this derivation is associated with distinct nodes in the tree, so there must be at least one step involved in the derivation. Consider for instance a derivation of the form \( A \Rightarrow BA \Rightarrow^\ast vA \), where \( B \Rightarrow^\ast v \). Here we have \( x = \varepsilon \) and we know that \( v \neq \varepsilon \), since a Chomsky normal form grammar cannot derive the empty string. More in general, one can have a derivation of the form \( A \Rightarrow B_1C_1 \Rightarrow B_1B_2C_2 \Rightarrow \cdots \Rightarrow B_1B_2 \cdots B_{k-1} C_{k-1} \Rightarrow B_1B_2 \cdots B_{k} A \Rightarrow^\ast vA\), again with \( x = \varepsilon \) and \( v \neq \varepsilon \).

An entirely symmetrical argument could be made for derivations of the form \( A \Rightarrow^\ast Ax \) with \( v = \varepsilon \) and \( x \neq \varepsilon \).