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 2022 in Semester 2 at Clayton and Malaysia. It has no prerequisites and unlocks 3 units, leading on to 6 units in all. Students rate it 4.0 out of 5 from 1 review and call it hard.
This is the 2022 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.
No prerequisites or corequisites besides the enrolment rules below.
3 units list FIT2014 as a prerequisite or corequisite.
Prerequisite:
AND
Prohibition:
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 | On campus |
| 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 activities. The unit requires on average three/four hours of scheduled activities per week. Scheduled activities may include a combination of teacher directed learning and online engagement.
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 2022 handbook.
FIT2014 has no prerequisites, but enrolment rules apply.
FIT2014 is a prerequisite or corequisite for 3 units, including MTH2137, MTH3170 and MTH3175. Those lead on to 6 units in all.
In 2022, 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.