Faculty of Information Technology
FIT2014 Theory of computation is a level 2, 6-credit-point, undergraduate unit from the Faculty of Information Technology, offered in 2024 in Semester 2 at Clayton and Malaysia. It needs (FIT1054, MTH2140, FIT2085, MTH3140, FIT1008, MTH2021, MTH2141, MTH2025 or MTH3141) and (MAT1830, MTH1035 or ATS2866) and unlocks 3 units, leading on to 16 units in all. Students rate it 4.0 out of 5 from 1 review and call it hard.
This is the 2024 handbook entry. See the 2027 entry.
Theory of computation is abstract at first but really satisfying once automata and Turing machines click. Less directly practical than other units, but it changes how you think about problems. Keep up with the tutorials, the later weeks build on everything.
Pass these before you enrol.
3 units list FIT2014 as a prerequisite or corequisite.
Prerequisites: Students should have some prior experience with (a) programming, (b) algorithm analysis, (c) logic, and (d) rigorous proofs using logical reasoning (not just algebraic manipulation).
This unit introduces formal languages, models of computation, and computational complexity. It looks at what computers can and cannot compute. Topics include finite state automata, regular expressions, grammars, pushdown automata, computable functions, Turing machines, polynomial-time reductions, complexity classes P and NP, and NP-completeness. Skills at writing formal proofs will be developed.
| Teaching period | Campus | Mode |
|---|---|---|
| Second semester | Clayton | Flexible |
| Second semester | Malaysia | On campus |
When you finish this unit, you should be able to:
Use propositional logic, predicates and quantifiers to represent and analyse problems in the theory of computation;
Construct Finite Automata, Nondeterministic Finite Automata and Context-Free Grammars to describe languages;
Convert Regular Expressions into Finite Automata and vice versa;
Find a Regular Grammar for a Regular Language;
Find a parse tree, leftmost derivation and rightmost derivation for a word in a Context Free Language;
Use Turing Machines to describe languages and represent computable functions;
Demonstrate the limitations of the models of computation considered;
Show a language is not regular, or not context-free, or not decidable;
Show that a language is in P, or in NP, or NP-complete;
Write rigorous formal proofs, including proofs by construction, cases, contradiction and induction.
Minimum total expected workload to achieve the learning outcomes for this unit is 144 hours per semester typically comprising a mixture of scheduled online and face to face learning activities and independent study. Independent study may include associated reading and preparation for scheduled teaching activities.
Sipser, M., 2013, Introduction to the theory of computation, 3rd Edition, Cengage Learning, Boston, MA
Turing machine simulator, Tuatara (version 2.1), as well as Linux.
FIT2014 is part of 7 areas of study in the 2024 handbook.
You need (FIT1054, MTH2140, FIT2085, MTH3140, FIT1008, MTH2021, MTH2141, MTH2025 or MTH3141) and (MAT1830, MTH1035 or ATS2866) before you enrol. Enrolment rules also apply.
FIT2014 is a prerequisite or corequisite for 3 units, including MTH2137, MTH3170 and MTH3175. Those lead on to 16 units in all.
In 2024, FIT2014 runs in Semester 2 at Clayton and Malaysia.
Students who took it rate it hard to do well in and moderate on workload (1 rating). The handbook expects about 144 hours of study across the semester.
Yes. The exam is worth 50% of the final mark, alongside 4 other tasks.
FIT2014 is part of Computational science, Computer science, Mathematics and Pure mathematics.
It is rated 4.0 out of 5 from 1 review. Read the reviews above or add your own.