Tutorial workbook
Where each of the 20 tutorial sessions is covered on this site, so you can find the practice problems for any session.
The course's tutorial workbook has 20 sessions. Their problems are included, without answers, in the Tutorial problems section of the matching topic page.
Problems that depend on a drawn automaton have been replaced by similar problems that you can do from the text alone.
| Session | Workbook title | Topic page(s) |
|---|---|---|
| 1 | Finite automata: DFA | Topic 1 |
| 2 | Finite automata: NFA | Topic 2 |
| 3 | DFA–NFA equivalence | Topic 2 |
| 4 | Regular expressions | Topic 3 |
| 5 | Conversion from NFA, DFA to RE and back | Topic 3, Topic 4 |
| 6 | DFA minimisation | Topic 5 |
| 7 | Regular grammar and pumping lemma for regular languages | Topic 8, Topic 9 |
| 8 | Context-free grammar | Topic 10 |
| 9 | Design of CFG: derivations, parse trees, LMD, RMD, ambiguity | Topic 11 |
| 10 | CFG simplification | Topic 12 |
| 11 | Normal form: CNF | Topic 13 |
| 12 | Normal form: GNF | Topic 13 |
| 13 | Pushdown automata, PDA–CFG equivalence | Topic 14, Topic 16 |
| 14 | CFG–PDA equivalence, properties of CFL, pumping lemma for CFL | Topic 16, Topic 17, Topic 18 |
| 15 | Turing machines | Topic 21, Topic 22 |
| 16 | Designing Turing machines for computing functions | Topic 22 |
| 17 | Recursive and recursively enumerable languages | Topic 24 |
| 18 | Universal Turing machine | Topic 25 |
| 19 | Chomsky hierarchy and halting problem | Topic 25 |
| 20 | Variants of TM: multi-tape and NDTM | Topic 26 |
Topics with no workbook session
Moore and Mealy machines (topics 6 and 7), PDA acceptance (topic 15), context-sensitive grammars (topic 19), linear bounded automata (topic 20) and TMs as acceptors (topic 23) are in the syllabus but have no workbook session. Their topic pages have their own tutorial problems.
How to use the problems
- Attempt each problem on paper, in full, before looking at any notes.
- Check your answer against the Key ideas and the Worked example on the topic page.
- Take the topic quiz. If you score below 60%, go back over the problems you found hardest.