[The University of Leicester]

Department of Mathematics & Computer Science



Next: MC214 Logic Programming Up: Year 2 Previous: MC208 Functional Programming

MC211 Automata, Languages and Computation

MC211 Automata, Languages and Computation

Credits: 20 Convenor: Prof. R. M. Thomas Semester: 1
Prerequisites: essential: MC111 or MC144 desirable: MC103 or equivalent
Assessment: Continual assessment: 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

Explanation of Pre-requisites

There is not very much in the way of pre-requisite knowledge required for this module. Our main purpose is to reason about the nature of computation; this is done by giving mathematical models for computational devices and then by investigating what tasks these abstract machines can perform. In order to form these models, we need the basic concepts of sets, relations and functions as introduced in MC111 or MC144; either of those modules provides all that we need here.

In order to help understand the motivation for studying these models, it would be helpful to have done some programming before, such as that undertaken in MC103; 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 in the course, 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.

This material will be described in the lectures (three per week); there will also be a weekly surgery session (for sorting out problems, including difficulties with the assessed work) and a problem class (for going through the previous worksheet). A full set of printed lecture notes for the module is also available.

Aims

The first aim of this module is to give an understanding of the basic theory of language recognition with applications in areas such as compiler design. The course 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. By the end of the module the students should be able to comprehend abstract models of the process of computation and produce reasoned arguments about the power of such models. They should have some awareness of the significance of these models in different areas of Computer Science.

Objectives

By the end of the module the students should be familiar with the fundamental models introduced in the course. They should be able to follow basic mathematical arguments couched in terms of these models and also be capable of constructing such arguments for themselves. They should be capable of writing such arguments clearly and correctly with proper use of mathematical notation. In addition, they should have understood the various specific techniques covered in the module and be able to perform these techniques in practice.

Transferable Skills

The main purpose of this course is to provide mathematical models of the process of language recognition and computation. These are fundamental structures and grasping this material will allow students to pursue further study in areas ranging from compiler design through to computability and complexity.

Apart from the widespread use of these models, the study of the material in this course should help students develop their general ability to think abstractly and, consequently, provide them with the ability to be adaptable in a fast-changing subject area. In addition, the module should make a contribution to the general development of problem-solving skills.

Syllabus

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

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

Grammars. Terminals and non-terminals. Regular grammars. Equivalence of regular grammars and finite automata. Closure properties of regular languages. Empty moves. Regular expressions. Converting a machine to a regular expression.

Stacks. Pushdown automata and context-free grammars. Emptying the stack. Parse trees. Leftmost and rightmost derivations. Ambiguous grammars. Inherent ambiguity. Equivalence of pushdown automata and context-free grammars. Limitations of context-free grammars. Closure properties of context-free languages. Pascal is not context-free. Deterministic context-free languages. LL-parsers.

Turing machines. Completing a Turing machine. Extensions of Turing machines. The Church-Turing Thesis. Non-determinism. Decision-making Turing machines. Recursive languages. Universal Turing machines. Existence of Turing acceptable languages that are not recursive. The halting problem. Further examples of unsolvable problems. Other models of computation (phrase-structure grammars, register machines and programming languages).

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

Reading list

Background:

H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 1981.

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.

J. E. Hopcroft and J. E. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979 (out of print, but copies available in the Library).

T. W. Parsons, Introduction to Compiler Construction, W. H. Freeman, 1992.

T. Sudkamp, Languages and Machines, Addison Wesley, 1988.

C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1994.

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

Details of Assessment

The coursework for the continual assessment consists of weekly problem sheets throughout the module. Any problems with these can be discussed in the surgeries preceding the hand-in. Your work will be marked and then gone through in a problem class.

The written January examination will contain six questions. These are equally weighted; any number of questions may be attempted, but only the best four answers will be taken into account.

Next: MC214 Logic Programming Up: Year 2 Previous: MC208 Functional Programming

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

Author: S. J. Ambler, tel: +44 (0)116 252 3884
Last updated: 2001-09-20
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.