Monash University Handbook 2010 Undergraduate - Unit
FIT2014 - Theory of computation
6 points, SCA Band 2, 0.125 EFTSL
Synopsis
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.
Objectives
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.
Assessment
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
Prerequisites
FIT1008 or FIT1015 or CSE1303 and two of (or one completed and one enrolled) from MAT1830, MAT1841, MTH1020, MTH1030, MTH1112, MTH2010
Prohibitions
CSE2303
Additional information on this unit is available from the faculty at:
http://www.infotech.monash.edu.au/units/fit2014