**Next:**Software Design

**Up:**Lent Term 2008: Part

**Previous:**Programming in Java

**Contents**

##

Regular Languages and Finite Automata

This course is taken by Part IA (50% Option) students.

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

**Next:**Software Design

**Up:**Lent Term 2008: Part

**Previous:**Programming in Java

**Contents**