One of the most engaging teams, for some of the most fascinating content in FIT.
- Teaching5out of 5
- Content5out of 5
- Assessment5out of 5
- Usefulness5out of 5
- DifficultyHard
- WorkloadModerate
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 2025 in Semester 1 and Semester 2 at Clayton and Malaysia. It needs (FIT1008, FIT1054, MTH2140, FIT2085, MTH3140, MTH2021, MTH2141, MTH2025 or MTH3141) and (FIT1058, MAT1830, MTH1035 or ATS2866) and unlocks 4 units, leading on to 17 units in all. Students rate it 5.0 out of 5 from 3 reviews and call it hard.
This is the 2025 handbook entry. See the 2027 entry.
One of the most engaging teams, for some of the most fascinating content in FIT.
I liked the content, pre hard at times but useful for your degree and future career
This unit helped me understand computation more deeply and is definitely useful as a lot of things in software engineering are just secretly finite state machines... teaching team was GREAT all around, however it is a tad bit on the hard side compared to other units
Pass these before you enrol.
4 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 |
|---|---|---|
| First semester | Clayton | Flexible |
| First semester | Malaysia | On campus |
| 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 2025 handbook.
You need (FIT1008, FIT1054, MTH2140, FIT2085, MTH3140, MTH2021, MTH2141, MTH2025 or MTH3141) and (FIT1058, MAT1830, MTH1035 or ATS2866) before you enrol. Enrolment rules also apply.
FIT2014 is a prerequisite or corequisite for 4 units, including FIT3185, MTH2137, MTH3170 and MTH3175. Those lead on to 17 units in all.
In 2025, FIT2014 runs in Semester 1 and Semester 2 at Clayton and Malaysia.
Students who took it rate it hard to do well in and moderate on workload (3 ratings). The handbook expects about 144 hours of study across the semester.
Yes. The exam is worth 65% of the final mark, alongside 4 other tasks.
FIT2014 is part of Computational science, Computer science, Mathematics and Pure mathematics.
It is rated 5.0 out of 5 from 3 reviews, and 3 students of 3 gave it 4 or 5 stars. Read the reviews above or add your own.