UnitLevel 2Undergraduate

FIT2014 Theory of computation

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 2026 in Semester 1 and Semester 2 at Clayton and Malaysia. It needs (FIT1008, FIT1054, FIT2085, MTH2021, MTH2025, MTH2140, MTH3140, MTH2141 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.

Credit points
6
Offered in 2026
Semester 1, Semester 2
Clayton, Malaysia
Assessment
Exam 65%
and 3 other tasks
Workload
144 hours
per semester

This is the 2026 handbook entry. See the 2027 entry.

Reviews

Rated 5.0 out of 5 from 3 reviews
5.03 reviews
  1. 5 stars: 3
  2. 4 stars: 0
  3. 3 stars: 0
  4. 2 stars: 0
  5. 1 star: 0
Teaching
4.7out of 5 from 3 reviews
Content
4.7out of 5 from 3 reviews
Assessment
4.7out of 5 from 3 reviews
Usefulness
4.7out of 5 from 3 reviews
Difficulty
Hard
Workload
Moderate

What students say

  • JL9 November 2026
    5 out of 5: Excellent

    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
  • M15 October 2026 - Took it in 2025
    5 out of 5: Excellent

    I liked the content, pre hard at times but useful for your degree and future career

    • Teaching4out of 5
    • Content4out of 5
    • Assessment4out of 5
    • Usefulness4out of 5
    • DifficultyHard
    • WorkloadHeavy
  • JS5 October 2026 - edited - Took it in 2025
    5 out of 5: Excellent

    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

    • Teaching5out of 5
    • Content5out of 5
    • Assessment5out of 5
    • Usefulness5out of 5
    • DifficultyHard
    • WorkloadModerate

Requisites

Overview

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.

Offerings in 2026

Teaching periodCampusMode
First semesterClaytonFlexible
First semesterMalaysiaOn campus
Second semesterClaytonFlexible
Second semesterMalaysiaOn campus

Assessment

  • Practical PreparationWrittenThreshold hurdle
    5%
  • Assignment 1: Regular Expressions and Finite AutomataProjectThreshold hurdle
    10%
  • Mid-semester TestExaminationThreshold hurdle
    15%
  • Assignment 2: Lexical Analysis, Parsing, ComputabilityProjectThreshold hurdle
    20%
  • Scheduled final assessment (3 hours and 10 minutes)ExaminationThreshold hurdle
    50%

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

Learning outcomes

When you finish this unit, you should be able to:

  1. 1

    Use propositional logic, predicates and quantifiers to represent and analyse problems in the theory of computation;

  2. 2

    Construct Finite Automata, Nondeterministic Finite Automata and Context-Free Grammars to describe languages;

  3. 3

    Convert Regular Expressions into Finite Automata and vice versa;

  4. 4

    Find a Regular Grammar for a Regular Language;

  5. 5

    Find a parse tree, leftmost derivation and rightmost derivation for a word in a Context Free Language;

  6. 6

    Use Turing Machines to describe languages and represent computable functions;

  7. 7

    Demonstrate the limitations of the models of computation considered;

  8. 8

    Show a language is not regular, or not context-free, or not decidable;

  9. 9

    Show that a language is in P, or in NP, or NP-complete;

  10. 10

    Write rigorous formal proofs, including proofs by construction, cases, contradiction and induction.

Workload and teaching

  • Seminars36 hours
  • Applied sessions24 hours
  • Workshops36 hours
  • Teaching approachEnquiry-based learning
  • Teaching approachActive learning
  • Teaching approachPeer assisted learning
  • Teaching approachProblem-based learning

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.

Learning resources

Recommended resources

Sipser, M., 2013, Introduction to the theory of computation, 3rd Edition, Cengage Learning, Boston, MA

Sydney Padua, The Thrilling Adventures of Lovelace and Babbage, Penguin, 2016. ISBN:  978-0-141-98153-6

Technology resources

Turing machine simulator, Tuatara (version 2.1), as well as Linux.

Where it fits

FIT2014 is part of 7 areas of study in the 2026 handbook.

Contacts

Chief Examiners
Professor Graham Farr
Unit Coordinators
Dr Mohd Fikree Hassan
Professor Wong Kok Sheik

Common questions

What are the prerequisites for FIT2014?

You need (FIT1008, FIT1054, FIT2085, MTH2021, MTH2025, MTH2140, MTH3140, MTH2141 or MTH3141) and (FIT1058, MAT1830, MTH1035 or ATS2866) before you enrol. Enrolment rules also apply.

What can I take after FIT2014?

FIT2014 is a prerequisite or corequisite for 4 units, including FIT3185, MTH2137, MTH3170 and MTH3175. Those lead on to 17 units in all.

When is FIT2014 offered?

In 2026, FIT2014 runs in Semester 1 and Semester 2 at Clayton and Malaysia.

Is FIT2014 hard?

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.

Does FIT2014 have an exam?

Yes. The exam is worth 65% of the final mark, alongside 4 other tasks.

Which majors and minors include FIT2014?

FIT2014 is part of Computational science, Computer science, Mathematics and Pure mathematics.

What do students think of FIT2014?

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.

More details

Credit points
6
Level
2
Study level
Undergraduate
Faculty
Faculty of Information Technology
Type
Coursework
EFTSL
0.125
Student contribution
SCA Band 2
Study abroad
Available