CS259 15 CATS (7.5 ECTS) Term 2

Availability

Core - CS, CMS, DM

Note: This module is only available to students in the second year of their degree and is not available as an unusual option to students in other years of study.

Academic Aims

The module introduces methods used to describe and reason about formal languages (such as programming languages). It presents a classification of formal languages (Chomsky hierarchy) and techniques for locating languages within it (closure properties, pumping lemmas). Automata models corresponding to various levels of the Chomsky hierarchy are discussed along with the fundamental notion of computability. These concepts are central to computer science.

Learning Outcomes

On completion of the module the student will be able to:

• Specify formal languages.

• Translate between various forms of formal language descriptions.
• Argue that given formal languages are (or are not) regular or context-free.
• Understand the operation of tools for lexical analysis and parsing.
• Understand ideas of decidability and the Church-Turing thesis.

Content

• Regular languages: finite automata, non-determinism, regular expressions, pumping lemma,non-regular languages, minimisation, translations between automata and regular expressions, closure properties
• Context-free languages: context-free grammars, ambiguity, Chomsky normal form, pushdown automata, pumping lemma, translations between automata and grammars, closure properties
• Introduction to lexical analysis and parsing
• Turing-recognisable languages: Turing machines, Church-Turing thesis, decidability, reducibility, the halting problem

Books

• M. Sipser, Introduction to the Theory of Computation, 3rd Edition, Cengage, 2013
• J.E. Hopcroft, R.Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation,
3rd Edition, Prentice Hall, 2006

Assessment

Two hour examination (70%), coursework (30%)

Teaching

30 lectures and 10 seminars