Monash University

Offered

Clayton Second semester 2008 (Day)
Sunway Second semester 2008 (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:

1. How to describe languages using Regular Expressions, Finite Automata, Nondeterministic Finite Automata, Mealy Machines, Moore Machines, Context Free Grammars, Pushdown Automata, and Turing Machines.;
2. The relationship between Regular Languages, Context Free Languages, Recursive Languages, and Recursive-Enumerable (or Computable) Languages;
3. How to use Turing Machines to represent computable functions;
4. How a Universal Turing machine can simulate any Turing Machine on any input;
5. 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:

1. Appreciate the limitations of Regular Languages, Context Free Languages, Recursive Languages, and Computable Languages;
2. Comprehend the limitations of computers in terms of the problems they can solve.

At the completion of this unit, students will be able to:

1. Construct Finite Automata, Nondeterministic Automata, and Turing Machines to describe languages;
2. Use Finite Automata to construct lexical analysers;
3. Use lexical analyser generator to construct lexical analysers;
4. Convert Regular Expressions into a Finite Automata;
5. Convert Finite Automata into Regular Expressions;
6. Use a compiler complier to construct parsers;
7. Find a Regular Grammar for a Regular Language;
8. Find a parse tree, leftmost derivation and rightmost derivation for a word in a Context Free Language;
9. Know how to show a Context Free Grammar is ambiguous;
10. 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