Regular Languages and Finite Automata
2009–10

Principal lecturer: Prof Andrew Pitts
Taken by: Part IA CST

• Syllabus.
• Lecture notes and slides [pdf].
• Past exam questions: recent ones (1993-2009) are here; older ones (1988-92) are available here, courtesy of David Allsopp (dra27 at cantab.net).
• Feedback: Please proved feedback through the online lecture course feedback form.
• Further resources:
  • Alley Stoughton's Forlan tools for experimenting with formal languages within Standard ML.
  • Russ Cox's article Regular Expression 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 speeds.")