## Department of Mathematics & Computer Science | ||||

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: |
94 |

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, 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.

Phrase-structure grammars. Terminals and non-terminals. Regular grammars. Equivalence of regular grammars and finite automata. Closure properties of regular languages. Empty moves. Regular expressions.

Stacks. Pushdown automata and context-free grammars. Syntax diagrams and EBNF. Parse trees. Leftmost and rightmost derivations. Equivalence of pushdown automata and context-free grammars. Ambiguous grammars. Inherent ambiguity. Limitations of context-free grammars. 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. Decision-making Turing machines. Recursive languages. Existence of Turing acceptable languages that are not recursive. The halting problem. The Church-Turing Thesis. Further examples of unsolvable problems.

Complexity. Space and time complexity and the relationship betwen them. Decision making versus acceptance. Determinism versus non-determinism; P and NP. Hierarchy theorems. Reductions and completeness.

**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. Harel**,
*Algorithmics, the Spirit of Computing, 2nd edition*,
Addison Wesley, 1992.

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

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

Last updated: 2003-09-23

MCS Web Maintainer

This document has been approved by the Head of Department.

© University of Leicester.