Lecture 19: 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.

Is the implementation of the acceptor from the previous lecture really sound? We will see how difficult it is to write a programming that behaves according to specification. We will cast a little light on the questions related to specifications, implementations, and correctness.

The main result of this lecture is that we examine a fix of a problem presented in the previous lecture. .

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 18
Next lecture: Lecture 20