*Lecturer: Dr A.M. Pitts* (`ap@cl.cam.ac.uk`)

*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 books**

Kozen, D.C. (1997). *Automata and Computability*. Springer-Verlag.

Sudkamp, T.A. (1988). *Languages and Machines*. Addison-Wesley.