Context free grammars

See Kozen (1997) lectures 19, 20

CNF and GNF cannot generate $ϵ$.

• Replace single letters with non-terminals
• Remove $ϵ$
• Remove unit productions.
• Remove productions of length greater than $2$.k

Theorem 35.1(Pumping lemma for CFLs, Hopcroft et al. (2007) 7.18).

Let $L$ be a CFL. Then there exists a constant $n$ such that if $z$ is any string in $L$ such that $|z|$ is at least $n$, then we can write $z=uvwxy$, subject to the following conditions:

1. $|vwx|\le n$.
2. $vx\ne ϵ$.
3. For all $i\ge 0$, $u{v}^{i}w{x}^{i}y\in L$.

---

References

Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2007). Introduction to Automata Theory, Languages, and Computation (3. ed). Pearson.

Kozen, D. C. (1997). Automata and Computability. Springer New York. https://doi.org/10.1007/978-1-4612-1844-9