Normal Forms: Chomsky Normal Form and Greibach Normal Form
Every context-free grammar can be rewritten so that each rule has the same tidy shape, and tidy shapes make proofs and parsers simple.
What this unit covers
Unit 4: Formal Grammars and Context-Free Languages
- 1 Formal Grammars and the Chomsky HierarchyAutomata check sentences; grammars write them, and four kinds of grammar sort every language into a ladder. · 13 min
- 2 Context-Free Grammars, Derivations and Parse TreesThe same sentence can be built in many orders, but a parse tree records only what was built, not when. · 12 min
- 3 Ambiguity in Context-Free GrammarsWhen one sentence has two parse trees, a calculator can honestly disagree with itself about 2 + 3 × 4. · 12 min
- 4 Simplification of Context-Free GrammarsBefore a grammar can be put into a standard shape, clear out the dead rules, the empty rules and the rules that only rename. · 13 min
- 5 Normal Forms: Chomsky Normal Form and Greibach Normal FormEvery context-free grammar can be rewritten so that each rule has the same tidy shape, and tidy shapes make proofs and parsers simple. · 14 min