Faculty of Information Technology

Skip to content | Change text size

print version

Monash University

Monash University Handbook 2010 Undergraduate - Unit

6 points, SCA Band 2, 0.125 EFTSL

FacultyFaculty of Information Technology
OfferedClayton Second semester 2010 (Day)
Sunway Second semester 2010 (Day)
Coordinator(s)Dr Kevin Korb (Clayton); Mr Loke Kar Seng (Malaysia)


This unit looks at the question of exactly what a computer can compute, and gives an introduction to formal languages. Topics include computable functions, finite state automata, regular expressions, grammars, translators, and Turing computability.


At the completion of this unit students will have -
A knowledge and understanding of:

  • how to describe languages using Regular Expressions, Finite Automata, Nondeterministic Finite Automata, Mealy Machines, Moore Machines, Context Free Grammars, Pushdown Automata, and Turing Machines;
  • the relationship between Regular Languages, Context Free Languages, Recursive Languages, and Recursive-Enumerable (or Computable) Languages;
  • how to use Turing Machines to represent computable functions;
  • how a Universal Turing machine can simulate any Turing Machine on any input;
  • compiler generation tools and the ability to use these to create simple compilation/translation programs.
Developed attitudes that will allow them to:
  • appreciate the limitations of Regular Languages, Context Free Languages, Recursive Languages, and Computable Languages;
  • comprehend the limitations of computers in terms of the problems they can solve.
Developed the skills to:
  • construct Finite Automata, Nondeterministic Automata, and Turing Machines to describe languages;
  • use Finite Automata to construct lexical analysers;
  • use lexical analyser generator to construct lexical analysers;
  • convert Regular Expressions into a Finite Automata;
  • convert Finite Automata into Regular Expressions;
  • use a compiler complier to construct parsers;
  • 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;
  • know how to show a Context Free Grammar is ambiguous;
  • convert Mealy Machines and Moore Machines into sequential logic circuits.


Examination (3 hours): 70%; In-semester assessment: 30%

Chief examiner(s)

Dr Kevin Korb

Contact hours

2 hrs lectures/wk, 3 hr laboratory/fortnight, 1 hr tutorial/fortnight


FIT1008 or FIT1015 or CSE1303 and two of (or one completed and one enrolled) from MAT1830, MAT1841, MTH1020, MTH1030, MTH1112, MTH2010



Additional information on this unit is available from the faculty at: