Course pages 2012–13
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 (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.
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.