Computer Laboratory

Course material 2010–11

Regular Languages and Finite Automata

Principal lecturer: Dr Marcelo Fiore
Taken by: Part IA CST
Syllabus
Past exam questions

Lecture notes

Lecture slides

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.")
    • Feedback
  • Please provide feedback through the online lecture course feedback form.