Context-free languages
Grammars that generate nested structure, the CYK algorithm that decides membership by dynamic programming, and pushdown automata, finite machines with a stack.
About 5 hours of study
Learning objectives
- Write grammars and follow derivations and parse trees
- Parse with CYK in Chomsky normal form
- Simulate deterministic and nondeterministic pushdown automata
Lessons
- 1
Context-free grammars Advanced
A grammar generates a language with rewriting rules. Write grammars for aⁿbⁿ, balanced brackets and arithmetic, follow derivations and parse trees, spot ambiguity, and generate a grammar's strings in Python.
- 2
Parsing with the CYK algorithm Advanced
Decide whether a grammar generates a string with dynamic programming. Put the grammar in Chomsky normal form, fill a table of which variables produce each substring, and read the answer from the top cell.
- 3
Pushdown automata Advanced
Give a finite automaton a stack and it can count and match nesting. Simulate pushdown automata for aⁿbⁿ and balanced brackets in Python, and explore a nondeterministic one by searching its configurations.
Module practice
- Theory: Follow a derivationEasy
- Theory: All short strings of a grammarMedium
- Theory: Count the parse treesHard
- Theory: Is the grammar in Chomsky normal form?Easy
- Theory: Parse with CYKMedium
- Theory: Print the CYK tableHard
- Theory: Balanced brackets with a stackEasy
- Theory: A deterministic PDA for wcwᴿMedium
- Theory: Run any pushdown automatonHard
Module quiz
‹ Regular expressions and their limitsComputability and complexity ›