[The University of Leicester]

Department of Mathematics & Computer Science



Next: CO2014 Logic Programming Up: Year 2 Previous: CO2008 Functional Programming

CO2011 Automata, Languages and Computation

CO2011 Automata, Languages and Computation

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

Subject Knowledge

Aims

The aim of this module is to give an understanding of the basic theory of language recognition motivated by applications in areas such as compiler design. The module will also aim to provide a general model of computation and thereby to illustrate the limits of the power of computers, both in terms of the problems for which a solution exists and also the problems for which a feasible solution exists.

Learning Outcomes

By the end of the module students should be able to comprehend some abstract models of the process of computation such as finite automata, pushdown automata and Turing machines. They should be able to follow basic mathematical arguments couched in terms of these models.

Methods

Class sessions together with course notes, worksheets and web support. Recommended textbooks for extra information and supplementary reading.

Assessment

Marked weekly coursework and a written examination.

Subject Skills

Aims

To teach students a range of comprehension, writing and problem-solving skills.

Learning Outcomes

Students should be able to solve problems and produce reasoned arguments about the power of the computational models studied in the course (using their understanding of these models to break down and analyze the problems). They should be capable of writing such arguments clearly and correctly with a proper use of mathematical notation where appropriate.

Methods

Class sessions together with worksheets.

Assessment

Marked weekly coursework and a written examination.

Explanation of Pre-requisites

There is not much in the way of pre-requisite knowledge required for this module. We need the basic concepts of sets, logic, relations and functions as introduced in CO1011 or MA1101; either of these provides all that we need here. In order to help understand the motivation, it would be helpful to have done some programming before, such as that undertaken in CO1003; however, while previous experience of programming is desirable, it is not essential. Some of the methods in this module are expressed in a sort of pseudocode notation, but there is no actual programming content. and a student who had not done programming before could still take this module if he/she wanted to. Such students are welcome to discuss their suitability for the course with the module convenor.

Course Description

In this course we are primarily concerned with what computers can do. It turns out that there are problems that cannot be solved by computer, or, at least, by machines corresponding to the mathematical models of computers we shall present. It is clearly sensible to investigate which problems cannot be solved; there is no point trying to program a computer to solve a problem that is unsolvable! A problem may be unsolvable in the sense that no computer program exists that will solve it or in the sense that any program that would solve it would take longer than the lifetime of the universe to run. We will give some precise mathematical models of the process of computation. Within these models, we will see what sort of tasks can be performed.

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.

Syllabus

This is currently under review and may alter slightly for 2003/4.

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.

Reading list

Background:

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.

Resources

Course notes, web page, study guide, worksheets, lecture rooms with board space and two OHPs, past examination papers.

Module Evaluation

Course questionnaires, course review.

Next: CO2014 Logic Programming Up: Year 2 Previous: CO2008 Functional Programming

[University Home] [MCS Home] [University Index A-Z] [University Search] [University Help]

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.