# Computer Laboratory

Course pages 2012–13

# 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 (Continued into Easter term)
Suggested hours of supervisions: 3
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.

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.

• © 2012 Computer Laboratory, University of Cambridge
Information provided by Prof Andrew Pitts