**Next:**Part IB Assessed Exercise

**Up:**Easter Term 2009: Part

**Previous:**Paper 2: Probability

**Contents**

##

Paper 2: Regular Languages and Finite Automata

This Paper 2 course is taken by Part IA Computer Science Tripos students 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. (2005). *Languages and machines*. Addison-Wesley (3rd ed.).

**Next:**Part IB Assessed Exercise

**Up:**Easter Term 2009: Part

**Previous:**Paper 2: Probability

**Contents**