About complementing regular expressions (in Haskell)

See next post. 


I've been trying to code in Haskell a small program that, given a regular expression and an alphabet, would return the complement regular expression (with respect to the given alphabet).

First, let's set up the idea for the program. Simply working with the regular expression itself and trying to manipulate it directly would make the logic of the function be very cumbersome. So how should we go about it?

We're going to use the relation between DFAs, NFAs and regular expressions, namely:

• any regular expression can be represented as an NFA
• any NFA has an equivalent DFA
• any DFA can be complemented (very easily)
• any DFA can be represented through a regular expression.

Our battle plan will thus be:

• parse the regular expression
• convert it to a NFA
• convert the NFA to a DFA
• complement the DFA
• convert the DFA into a regular expression

This allows us to split up the program into manageable chunks which we will deal with separately. You can see the solutions for these in the few next posts.