Regular Languages and Finite Automata (50 per cent only)

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

No. of lectures: 6  

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 grammars

and the languages they generate.

Kleene's theorem.

The equivalence of regular expressions, finite automata and regular grammars for defining regular languages.

The Pumping Lemma

and its applications.

Recommended books:

Hopcroft, J.E. & Ullman, J.D. (1979). Introduction to Automata Theory, Languages and Computation. Addison-Wesley.

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