Aims and Fit of Module

1. To introduce formal concepts of automata, grammars and languages.
2. To introduce ideas of computability and decidability.
3. To illustrate the importance of automata, formal language theory and general models of computation in Computer Science and Artificial Intelligence.

Learning outcomes

At the end of the module student should:

1.Be familiar with the relationships between language as an object recognised by an automaton and as a set generated by a formal grammar.

2.Be able to apply standard translations between non-deterministic and deterministic automata.

3.Be familiar with the distinct types of formal grammar (e.g. Chomsky hierarchy) and the concept of normal forms for grammars.

4.Be aware of the limitations (with respect to expressive power) of different automata and grammar forms.

5.Understand the distinction between decidable and partially decidable languages.Recognise the significance of the Church-Turing hypothesis and its implications

Method of teaching and learning

Students will be expected to attend three hours of formal lectures as well as to participate in one hour of supervised problem classes in a typical week. Lectures will introduce students to the academic content and practical skills which are the subject of the module, while problem classes will allow students to practice those skills.
In addition, students will be expected to devote six hours of unsupervised time to solving continuous assessment tasks and private study. Private study will provide time for reflection and consideration of lecture material and background reading.
Continuous assessment will be used to test to what extent practical skills have been learnt.