|
University of Wales, Bangor - Department of Mathematics
Computer Science H1 Modules
|
|
|
IDM2015 Automata Theory
First semester 2006/2007
Lecturer: Dr Chris Wensley
Recommended books:
You might find the books listed below useful:
-
M.V. Lawson,
Finite Automata,
Chapman & Hall / CRC Press, 2003, ISBN: 1-58488-255-7.
-
D.I.A. Cohen, Introduction to computer theory,
second edition,
John Wiley and Sons, 1997, ISBN 0-471-13772-3.
-
E. Kinber and C. Smith, Theory of computing,
Prentice Hall, 2001, ISBN 0-13-027961-7.
What is automata theory?
Mathematicians and computer scientists use algorithms all the time,
but what exactly is an algorithm?
This question was only finally answered during the first few decades
of the twentieth century.
In fact, a number of different solutions were suggested
but, remarkably, they all turned out to be equivalent.
The one we shall study is due to Alan Turing,
who argued that algorithms can best be
described in terms of what are now known as `Turing machines'.
In this course, I shall build up to
the study of Turing machines in stages;
I will start with finite state automata,
then I shall study finite state automata equipped with extra
memory in the form of a pushdown stack, and finally I shall
study Turing machines themselves.
Pre-requisites:
IDM1015,
IDM1016.
From IDM1016 the section on finite state automata will be revised
during the first few lectures.
The ideas from IDM1015 needed are: trees, and general
background on sets and functions.
I shall also make use of some of the proof techniques I introduced in IDM1015.
Syllabus
Finite state automata
- Revision of first year work
Strings and languages, deterministic
finite state automata, non-deterministic automata, equivalence
of non-determinstic automata with deterministic automata.
New material: operations on languages.
- Non-deterministic automata with
ε-transitions
Algorithm for converting such machines to non-deterministic automata.
Machines for the product and Kleene star of languages.
- Regular expressions and regular languages.
- Kleene's theorem
Every regular language is recognisable and conversely.
Pushdown automata
- Phrase-structure grammars
Definition and examples;
the class of recursively enumerable (r.e.) languages.
- Context-free (CF) grammars and languages
Fragments of natural languages, fragments of computer languages, examples
from mathematics. Backus-Naur Form (BNF).
- Regular grammars
Recognisable languages are precisely the languages
described by regular grammars.
- Parsing and derivation trees
Leftmost and rightmost derivations, the meaning of ambiguity.
- The Pumping Lemma
The language
{a^n b^n c^n : n>0} is not CF.
- Pushdown automata
Every CF language is recognised by a
pushdown automaton (proof) and the converse (proof omitted).
Brief discussion of closure properties of CF languages,
and of deterministic pushdown automata and their languages.
Introduction to compilers.
Turing Machines
- Turing machines
Turing machines as language acceptors and as transducers (computers).
Languages accepted by Turing machines
are precisely the r.e. languages (proof omitted).
The Chomsky hierarchy of languages.
Introduction to partial recursive functions.
- Algorithms
What is an algorithm? Turing's thesis.
Encoding Turing machines as strings, brief introduction to
the universal Turing machine. An example of a language
which is not r.e.
Assessment
- Continuous assessment (4 assignments): 40%
- 1½ hour closed book end of semester examination: 60%