Course pages 2011–12

**Subsections**

##

Paper 2: Regular Languages and Finite Automata

This course is not taken by NST or PPST students.

*Lecturer: Professor A.M. Pitts*

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