COMP218

Decision, Computation and Language

Aims

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.

Syllabus

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

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 - authors Hopcroft and Ullman only - published in 1979)

Learning Outcomes

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 finite 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 recursive and recursively enumerable languages​.

Learning Strategy

Lectures and Tutorials

The module is taught by lectures at the rate of 3 per week to a total of 30 hours including two class tests of one hour each. Also, there will be one hour long tutorial each week.