• Exercise book: 200 Problems in Formal Languages and Automata Theory (errata).

Tutorials

1. 28/02/2019: problems 2 (parenthesis expressions) and 3 (semilinear sets).
2. 07/03/2019: problems 3 (semilinear sets), 10 (regular expression for sum in binary), 9, 11 (DFA for divisibility), 12 (NFA over one letter alphabet), and 13 (NFA for semilinear sets in binary).
3. 14/03/2019: closure properties of regular languages: union, intersection (NFA and DFA), reversal (p. 24), left/right quotients (p. 23), shuffle (p. 40), square root (p. 29); pumping lemma: primes not regular (p. 15.3), {a^mb^n | m!=n} (p. 15.5).
4. 21/03/2019: closure properties of regular languages: root (p. 30); minimal automata (p. 44); using Myhill-Nerode to prove non-regularity (palindromes, p. 16) and exponential lower bounds on minimal DFA (p. 63.1); parsing with NFA (p. 69).
5. 28/03/2019: long rejected words (p. 64); converting expressions to linear NFA; parsing with regular expressions (p. 70.2, 71).
6. 04/04/2019: context-free grammars: p. 83.1, 84.2, 86.1, 86.2, 87 (closure properties).
7. 11/04/2019: context-free grammars: 85.2, 88 (palindromes); unambiguous grammars: p. 90, 92.
8. 25/04/2019: CFL pumping lemma: p. 100, 103, 104, 106, 107; examples of: non-CFL with CFL complement, non-CFL with non-CFL complement.
9. 09/05/2019: Ogden's lemma: p. 101(2), 102: pushdown automata: p. 125, 133; deterministic pushdown automata: p. 137.
10. 16/05/2019: preservation of regularity for pushdown automata; examples of Turing machines: p. 160, 162: closure properties: p. 165.
11. 23/05/2019: two stacks p.170; one queue p. 171; 3 counters p. 172; 2 counters p. 177.
12. 30/05/2019: universality of grammars; Post problem; non-emptiness of intersection of two grammars.
13. 06/06/2019: unambiguity of grammars; summary of closure properties of languages in the Chomsky hierarchy.
14. 13/06/2019: write-once machines: p. 167. Examples from previous exams.