Automata & Formal Languages
A 20-module path through automata & formal languages, in study order from foundations to the frontier.
Modules
- Alphabets, Strings, and Languages
- Deterministic Finite Automata
- The Regular Languages
- Nondeterministic Finite Automata
- NFA-to-DFA Subset Construction
- Regular Expressions
- Equivalence of Regular Expressions and Finite Automata
- Closure Properties of Regular Languages
- The Pumping Lemma for Regular Languages
- Proving Languages Nonregular
- Context-Free Grammars
- Derivations and Parse Trees
- Ambiguity in Context-Free Grammars
- Chomsky Normal Form
- Pushdown Automata
- CFG-PDA Equivalence
- Closure Properties of Context-Free Languages
- The Pumping Lemma for Context-Free Languages
- Proving Languages Non-Context-Free
- Deterministic Context-Free Languages and Parsing