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 2021 in Semester 2 at Clayton and Malaysia. It has no prerequisites and unlocks 2 units, leading on to 4 units in all. Students rate it 5.0 out of 5 from 3 reviews and call it hard.
This is the 2021 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
No prerequisites or corequisites besides the enrolment rules below.
2 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 2021 handbook.
FIT2014 has no prerequisites, but enrolment rules apply.
FIT2014 is a prerequisite or corequisite for 2 units, including MTH3170 and MTH3175. Those lead on to 4 units in all.
In 2021, FIT2014 runs in 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 50% 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.