FIT3235 Theory of computation 1: Models of computation

This unit introduces the formal study of computation through languages, automata, grammars, and abstract computational models. It develops a rigorous understanding of how classes of languages can be specified and recognised, how computational models differ in expressive power, and where the fundamental limits of mechanised computation begin to appear. You will learn to construct and analyse finite automata, pushdown automata, grammars, regular expressions, and Turing-machine style models, and to write clear formal proofs about their properties and limitations. By focusing on languages and computational models, the unit provides the formal backbone for later study in complexity, compilers, logic, and functional programming languages.