Regular Languages and Finite Automata (50% option only)

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).

Regular expressions

for 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

and its applications.

Grammars,

context-free and regular. The class of regular languages coincides with the class of languages generated by a regular grammar.

Recommended books:

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

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