Course pages 2011–12

# Regular Languages and Finite Automata

**Principal lecturer:** Prof Andrew Pitts**Taken by:** Part IA CST**Past exam questions****Information for supervisors** (contact lecturer for access permission)

No. of lectures: 8

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 context-free grammars, and to explain their applications to computer languages.

## Lectures

**Regular expressions.**Specifying sets of strings by pattern-matching. [1 lecture]**Finite state machines.**Deterministic and non-deterministic finite automata and the languages they accept. [1 lecture]**Regular languages.**The language determined by a regular expression is regular and every regular language is determined by some regular expression. [2 lectures]**The Pumping Lemma.**Proof and applications. [1 lecture]**Context-Free grammars.**Context-free grammars. Backus-Naur form (BNF). Chomsky and Greibach normal forms. Regular grammars. The class of regular languages coincides with the class of languages generated by a regular grammar. [1 lecture]**Pushdown automata.**Pushdown automata and the languages they accept. A language is context-free if and only if it is accepted by some pushdown automaton. Forward look to Computation Theory. [2 lectures]

## 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 use the Pumping Lemma to prove that a given set of strings is not a regular language;
- be able to design a pushdown automaton to accept strings for a given context-free grammar.

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