Computer Laboratory

Course pages 2012–13

Regular Languages and Finite Automata

  • Lecture notes [pdf].
  • Slides [colour pdf]:
  • lecture 1
  • lecture 2
  • lecture 3
  • lecture 4
  • lecture 5
  • lecture 6
  • lecture 7
  • lecture 8
  • Exercise sheet [pdf].
  • List of corrections to the notes [pdf].
  • Past exam questions: recent ones (1993-2011) are here; older ones (1988-92) are available here, courtesy of David Allsopp (dra27 at cantab.net).
  • Further resources:
    • 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.")
    • The script of a stage play about regular expressions (really).
    • Matt Might's blog post about parsing context-free grammars using Brzozowski's derivatives.
    • Alley Stoughton's Forlan tools for experimenting with formal languages within Standard ML.