Context-Free Formal Language

A context-free formal language or a Type 2 language
is produced by the rules where is a variable, and .

Proposition

For a context free grammar and any word
there is a (not necessarily unique) Parse Tree such that .

Theorem

Every context free grammar
has a Chomsky Normal Form grammar
such that

Proof (sketch)

The product rules we need to kick out are:

1. Unit productions
2. bad productions where but
3. very bad productions where but contains terminal symbols.
   First kick the very bad productions out easily.
   Then add unit closure rules (for every and add rule )
   and prove that removing unit productions from a unit closed grammar
   doesn’t change the language.
   Then remove the bad productions
   by introducing a bunch of new variables for each of the bad productions
   and sticking them together.

Lemma

Context-Free Pumping Lemma