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

Lessons

  1. 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. 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. 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

Module quiz

1. Which grammar generates balanced brackets?
2. What memory does a pushdown automaton add to a finite automaton?
3. The grammar E → E+E | x gives x+x+x two parse trees. What is the grammar called?
4. In a CYK table, what does the cell for a substring hold?
5. Why can no deterministic PDA recognise even palindromes such as abba?
6. Which rule is NOT allowed in Chomsky normal form?

‹ Regular expressions and their limitsComputability and complexity ›