Pumping Lemma for CFLs & Non-Context-Free Proofs

The Pumping Lemma for CFLs is used to prove that a given language is NOT context-free.

Formal Statement:

If L is a context-free language, there exists a pumping length p ≥ 1 such that every string s \in L with |s| ≥ p can be divided into five pieces, s = uvxyz, satisfying:

1. |vxy| ≤ p (the pumped region vxy has length at most p).

2. |vy| ≥ 1 (v and y are not both empty; at least one symbol is pumped).

3. For all i ≥ 0: u v^i x y^i z \in L (both v and y are pumped simultaneously with identical powers).

Canonical Non-CFL Proofs:

- L_1 = { a^n b^n c^n \mid n ≥ 1 }: Pick s = a^p b^p c^p. Since |vxy| ≤ p, vxy can span at most two different symbol types (e.g., a's and b's, or b's and c's). Pumping changes the count of those symbols while leaving the third unchanged \implies Contradiction!

- L_2 = { a^n b^n c^n d^n \mid n ≥ 1 }: Not CFL (requires tracking 4 counts).

- L_3 = { w w \mid w \in \Sigma^* }: Not CFL (copying language requires cross-serial dependencies).

- L_4 = { a^{p} \mid p is prime }: Not CFL.

Unlike regular languages, many fundamental questions for CFGs are completely UNDECIDABLE:

Decidable Properties for CFGs:

1. Emptiness (L(G) = \emptyset): DECIDABLE (check if start symbol S derives any terminal string).

2. Finiteness (Is L(G) finite?): DECIDABLE (check for cycles in variable dependency graph of CNF).

3. Membership (w \in L(G)): DECIDABLE (via CYK dynamic programming algorithm in O(n^3)).

Undecidable Properties for CFGs (GATE Critical Traps):

1. Equivalence (L(G_1) = L(G_2)): UNDECIDABLE!

2. Totality / Universality (L(G) = \Sigma^*): UNDECIDABLE!

3. Inclusion (L(G_1) \subseteq L(G_2)): UNDECIDABLE!

4. Disjointness (L(G_1) \cap L(G_2) = \emptyset): UNDECIDABLE!

5. Is L(G) regular?: UNDECIDABLE!

6. Is grammar G ambiguous?: UNDECIDABLE!