# 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)

#### Offered

Clayton Second semester 2009 (Day)

Sunway Second semester 2009 (Day)

#### 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 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.

#### Assessment

Compulsory assessed laboratory classes: 30%; Examination: 70%.

#### Contact hours

8 x contact hrs/fortnight

#### Prerequisites

FIT1008 or FIT1015 (CSE1303) and 12 points (or 6 points completed and 6 points enrolled) from MAT1830, MAT1841, MTH1020, MTH1030, MTH1112, MTH2010.

#### Prohibitions

CSE2303, CSC2030

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

13 October 2017
06 December 2019