Compilers: Principles and Practice by Pearson

Formal Languages and Automata 431

This idea is the basis of the pumping lemma for a CFG. It will be easier if the grammar is in CNF.

Theorem A.5.5 (Pumping Lemma – 1

st

form) Let G = < V

N

, Σ, S, P > be a CFG expressed in

CNF, with a total of n NTs. If u ∈ L(G), | u | ≥ 2

n+1

, then u may be written as: u = vwxyz, for some v,

w, x, y and z, satisfying | wy | > 0, | wxy | ≤ 2

n+1

and this further implies that ∀ m ≥ 0, vw

m

xy

m

z ∈ L(G).

See Fig. A.18, in which the shaded portion – piece B – can be

iterated 0 or more times.

Theorem A.5.6 (Pumping Lemma – 2

nd

form) Here we

remove the requirement that the grammar should be given as

CNF. Let L be a CFL. ...