Lecture 15: Regular expressions.

Using the idea of continuations, we present in this lecture formally the notion of regular expressions. Regular expressions are extremely useful in computer science because they provide concise descriptions of languages.

The main result of this lecture is an acceptor for regular expressions.

Source Code:

acc.hs An acceptor for regular expressions in Haskell.

Suggested Reading Materials:

Robert Harper. Functional Pearls. Proof-Directed Debugging. Journal of Functional Programming, ????

Previous lecture: Lecture 14
Next lecture: Lecture 16