6 Simplification of Context-Free Grammars and Normal Forms
6.1 Methods for Transforming Grammars
A Useful Substitution Rule
Removing Useless Productions
Removing λ-Productions
Removing Unit-Productions
6.2 Two Important Normal Forms
Chomsky Normal Form
Greibach Normal Form
6.3 A Membership Algorithm for Context-Free Grammars*
7 Pushdown Automata
7.1 Nondeterministic Pushdown Automata
Definition of a Pushdown Automaton
The Language Accepted by a Pushdown Automaton
7.2 Pushdown Automata and Context-Free Languages
Pushdown Automata for Context-Free Languages
Context-Free Grammars for Pushdown Automata
7.3 Deterministic Pushdown Automata and Deterministic Context-Free
Languages
7.4 Grammars for Deterministic Context-Free Languages*
8 Properties of Context-Free Languages
8.1 Two Pumping Lemmas
A Pumping Lemma for Context-Free Languages
A Pumping Lemma for Linear Languages
8.2 Closure Properties and Decision Algorithms for Context-Free Languages
Closure of Context-Free Languages
Some Decidable Properties of Context-Free Languages.
9 Turing Machines
9.1 The Standard Turing Machine