Introduction to Formal Languages, Automata Theory and Computation

Chapter 8. Context-Free Grammars–Properties and Parsing

Pumping lemma for regular sets presented in an earlier chapter was used to prove that some languages are non-regular. Now, we give another pumping lemma for context-free languages (CFL) whose application will be to show that some languages are non-context-free. The idea behind this lemma is that longer strings in a CFL, have substrings which can be pumped to get infinite number of strings in the language.

Pumping Lemma for CFL

Theorem 8.1

Let L be a CFL. Then there exists a number k (pumping length) such that if w is a string in L of length at least ‘k,’ then w can be written as w = uυxyz satisfying the following conditions:

1. |υy| > 0

2. |υxy| ≤ k

3. For each i ≥ 0, uυⁱxyⁱz ∊ L

Proof. Let G be a context-free ...