Credits: 20 |
Convenor: Prof R M Thomas |
Semester: 1 |

Prerequisites: |
essential: CO1011 or MA1101 (or equivalent) | desirable: CO1003 (or equivalent) |

Assessment: |
Coursework: 30% | Three hour exam in January: 70% |

Lectures: |
36 | Problem Classes: |
12 |

Tutorials: |
none | Private Study: |
90 |

Labs: |
none | Seminars: |
none |

Project: |
none | Other: |
none |

Surgeries: |
12 | Total: |
150 |

At first sight, it may appear that these models are unduly simple and do not really capture all the subtleties of the process of computation. The advantages of using such models is two-fold. First, they are very simple to reason about, so that we can reach our conclusions much more simply than (for example) considering actual hardware and software components in fine detail. Second, they have proved to be very robust, in that successive generations of computers have all been shown to be no more powerful than the most general model we will present, and so the analysis based on these models has been useful throughout the history of Computer Science, whereas an analysis based on the specifics of various machines and programming languages quickly becomes obsolete.

Revision of mathematical pre-requisites (sets, logic, relations, graphs and functions). Strings. Formal languages. Operations on languages. Concatenation of strings. Kleene star.

Finite automata. Language acceptors. Regular languages. Equivalence. Complete automata. The concepts of determinism and non-determinism. The pumping lemma for regular languages. Examples of non-regular languages.

Grammars. Terminals and non-terminals. Regular grammars. Rewrite rules. Equivalence of regular grammars and finite automata. Closure properties of regular languages. Empty moves. Regular expressions. Equivalence of regular expressions and finite automata.

Stacks. Pushdown automata and context-free grammars. Emptying the stack. Parse trees. Leftmost and rightmost derivations. Equivalence of pushdown automata and context-free grammars. Ambiguous grammars. Inherent ambiguity. Closure properties of context-free languages. Are programming languages context-free? Deterministic context-free languages. Parsing. LL-parsers.

Turing machines. Extensions of Turing machines. Non-determinism. Church-Turing Thesis. Decision-making Turing machines. Recursive languages. Existence of Turing acceptable languages that are not recursive. The halting problem. Further examples of unsolvable problems.

Complexity. Space and time complexity and the relationship betwen them. Decision-making versus acceptance. Polynomial transformations. Determinism versus non-determinism. P and NP. NP-completeness. Examples of NP-complete problems.

**H. R. Lewis and C. H. Papadimitriou**,
*Elements of the Theory of Computation, second edition*,
Prentice Hall, 1998.

**J. E. Hopcroft, R. Motwani and J. D. Ullman**,
*Introduction to Automata Theory, Languages and Computation*,
Addison-Wesley, 2001.

**J. G. Brookshear**,
*Formal Languages, Automata and Complexity*,
Benjamin Cummings, 1989
(out of print, but copies available in the Library).

**D. Kelly**,
*Automata and Formal Languages - an Introduction*,
Prentice Hall, 1995
(out of print, but copies available in the Library).

**D. Wood**,
*Theory of Computation*,
Wiley, 1987
(out of print, but copies available in the Library).

**D. I. A. Cohen**,
*Introduction to Computer Theory*,
Wiley, 1986.

**J. Martin**,
*Introduction to Languages and the Theory of Computation*,
McGraw-Hill, 2003.

**P. Linz**,
*An introduction to Formal Languages and Automata*,
Jones and Bartlett, 2001.

Author: *N. Rahman*, tel: +44 (0)116 252 2593

Last updated: 2004-09-29

MCS Web Maintainer

This document has been approved by the Head of Department.

© University of Leicester.