![]() | Department of Mathematics & Computer Science | |||
![]() |
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 |
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.
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.
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.
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. 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. Reduced context-free grammars. Ambiguous grammars. Inherent ambiguity. Removing empty productions. Removing unit productions. Pumping lemma for context-free languages. Limitations of context-free grammars. Closure properties of context-free languages. Pascal is not context-free. Deterministic context-free languages. 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. Recursively enumerable sets. Equivalence of recursively enumerable and Turing acceptable. Phrase-structure grammars. Equivalence of phrase-structure grammars and Turing machines.
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.
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.
![]() ![]() ![]() ![]() ![]() |
Author: S. J. Ambler, tel: +44 (0)116 252 3884
Last updated: 10/4/2000
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.