Derivatives of Regular Expressions

In the advent of functional programming, the interest in the concept of derivatives of regular expressions [1] has been revived [2]. Apart from being elegant, it seems to be the only automata way of handling extended regular expressions, i. e. expressions including logical AND and NOT, which then can describe any boolean operations.

In this talk the notion of a derivative of a regular expression [1] will be introduced and the properties of derivatives will be discussed. This will lead in a natural way to the construction of a deterministic finite automaton from an extended regular expression.

[1] J. A. Brzozowski, "Derivatives of regular expressions", Journal of the Association for Computing Machinery, 11(4) (1964) 481-494

[2] Scott Owens, John Reppy, Aaron Turon, "Regular expression derivatives reexamined", Journal of Functional Programming, 19(2) (2009) 173-190