Mathematical preliminaries; regular languages, finite automata, and regular expressions; nondeterminism and determinism in finite automata; finite automata minimisation; properties of regular languages; nonregular languages; context-free languages, context-free grammars, and pushdown automata; nondeterminism and determinism in pushdown automata; properties of context-free languages; non-context-free languages; multi-stack machines; Turing machines and Church Turing thesis; de...
Learning Outcomes
Design the corresponding machine model to accept a specified language
Explain how some problems have no algorithmic solution
Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs, explain the Church-Turing thesis and its significance
Assess and prove the computational power required to decide a language