FIT3235 · Theory of computation 1: Models of computation

Overview

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.

Offerings

The Handbook publishes no offerings for this unit.

Assessment

The Handbook publishes no assessment items for this unit yet.

Assessment details may change. Please refer to the assessment information in Moodle closer to the start of the teaching period.

Requisites

Learning outcomes

1. Communicate formal arguments, proofs and machine constructions clearly in written, symbolic and visual forms appropriate to a technical audience;
2. Investigate questions about the expressive power and limits of computational models, evaluating alternative approaches and justifying conclusions through rigorous reasoning and counter-examples;
3. Construct and verify formal models of computation, including automata, grammars and Turing-machine style models, and reason about their properties using established proof techniques.

Workload

No workload detail published.

Student experience, not official rules. Nothing here changes what the Handbook says.