FIT2014 - Theory of computation
6 points, SCA Band 2, 0.125 EFTSL
Undergraduate Faculty of Information Technology
Leader(s): Associate Professor David Dowe (Clayton); Dr Mohammed Belkhatir (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 an 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;
- Knowledge of compiler generation tools and the ability to use these to create simple compilation/translation programs.
At the completion of this unit, students will have 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.
At the completion of this unit, students will be able 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.
Compulsory assessed laboratory classes: 30%; Examination: 70%.
8 x contact hrs/fortnight