- To introduce formal concepts of automata, grammars and languages.
- To introduce ideas of computability and decidability.
- To illustrate the importance of automata, formal language theory and general models of computation in Computer Science and Artificial Intelligence.
- 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)
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)
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
The module is taught by lectures at the rate of 3 per week to a total of 36. Two class tests are set.