** Next:** Structured Hardware Design (50%
** Up:** Easter Term 2004: Part
** Previous:** Operating Systems I
** Contents**

##

Regular Languages and Finite Automata
(50% option only)

*Lecturer: Dr A. Dawar*

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

* 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:** Structured Hardware Design (50%
** Up:** Easter Term 2004: Part
** Previous:** Operating Systems I
** Contents**
*Christine Northeast*

*Thu Sep 4 15:29:01 BST 2003
*