Monash University Handbook 2010 Undergraduate - Unit

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.

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

• 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