Regular Languages and Finite Automata
Principal lecturer: Prof Andrew Pitts
Taken by: Part IA CST
- Lecture notes and slides [pdf].
- Past exam questions: recent ones (1993-2009) are
older ones (1988-92) are available here,
courtesy of David Allsopp (dra27 at cantab.net).
- Feedback: Please proved feedback through the
course feedback form.
- Further resources:
- Alley Stoughton's
Forlan tools for
experimenting with formal languages within Standard ML.
- Russ Cox's article
Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP,
Python, Ruby, ...). (Summary: "Regular expression matching can be
simple and fast, using finite automata-based techniques that have been
known for decades. In contrast, Perl, PCRE, Python, Ruby, Java, and
many other languages have regular expression implementations based on
recursive backtracking that are simple but can be excruciatingly
slow. With the exception of backreferences, the features provided by
the slow backtracking implementations can be provided by the
automata-based implementations at dramatically faster, more consistent