Regular Languages and Finite Automata (50% option only)
Lecturer: Professor A.M. Pitts
No. of lectures: 6
This course is useful for Compiler Construction (Part IB)
and Natural Language Processing (Part II).
Aims
The aim of this short course will be to introduce the mathematical
formalisms of finite state machines, regular expressions and grammars,
and to explain their applications to computer languages.
Lectures
Regular expressions.
Specifying sets of strings by pattern-matching.
Finite state machines. Deterministic and
non-deterministic finite automata and the languages
they accept.
Regular languages I. The language determined by a regular
expression is regular.
Regular languages II. Every regular language is determined
by some regular expression.
The Pumping Lemma. Proof and applications.
Grammars. Context-free and regular grammars. The class of
regular languages coincides with the class of languages generated by
a regular grammar.
Objectives
At the end of the course students should
be able to explain how to convert between the three ways of
representing regular sets of strings introduced in the course; and
be able to carry out such conversions by hand for simple cases
be able to prove whether or not a given set of strings is
regular
Recommended reading
* Hopcroft, J.E., Motwani, R. & Ullman, J.D. (2001). Introduction to
automata theory, languages, and computation. Addison-Wesley (2nd ed.).
Kozen, D.C. (1997). Automata and computability. Springer-Verlag.
Sudkamp, T.A. (1988). Languages and machines. Addison-Wesley.