Aims

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.

Syllabus

• Preliminaries: principal mathematical ideas necessary to understand the material of the course (3 lectures)
• Finite automata and regular expressions: basic definitions,non-determinism, applications of finite automata (3 lectures)
• Properties of regular sets: pumping lemma, closure properties,decision algorithms, minimization of automata (6 lectures)
• Context-free grammars: introduction, derivation trees,simplification, Chomsky normal form, Greibach normal form (3 lectures)
• Pushdown automata: definitions, shared properties with context-free grammars (3 lectures)
• Properties of context-free grammars: pumping lemma, closure properties and decision algorithm (3 lectures)
• Chomsky hierarchy and deterministic context-free languages: normal form, closure, and application in parsing methods (6 lectures)
• Turing machines: Turing machine model, computable languages and functions, Church's hypothesis (6 lectures)
• Undecidability: recursive and recursively enumerable languages, universal Turing machines (3 lectures)

Recommended Texts

Supplementary Reading:
Introduction to Automata Theory, Languages and Computation. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Addison-Wesley, 2001
(not to be confused with a book of the same title published in 1979)

Learning Outcomes

At the end of the module student should:

• Be familiar with the relationships between language as an object recognised by an automaton and as a set generated by a formal grammar.
• Be able to apply standard translations between non-deterministic and deterministic automata.
• Be familiar with the distinct types of formal grammar (e.g. Chomsky hierarchy) and the concept of normal forms for grammars.
• Be aware of the limitations (with respect to expressive power) of different automata and grammar forms.
• Understand the distinction between decidable and partially decidable languages.
• Recognise the significance of the Church-Turing hypothesis and its implications

Learning Strategy

The module is taught by lectures at the rate of 3 per week to a total of 36. Two class tests are set.