find complement of regular expression
complement, regex
Solution
You need to go through the usual procedure:
- Convert regex to NFA.
- Convert NFA to DFA. For simple case, it is easy to convert (by hand) from regex to DFA directly.
- Turn all non-terminal state into terminal states and vice versa.
- Convert the complementing DFA to regex. This is one detailed example of such conversion
I won't show you the result since it is exercise, but I will show you the DFA for the first formula `(aa|bb)*`:
From this, you can see clearly that `a*` or `b*` will not give the correct result. You will never end up in the Trap state (which becomes a terminal state in the complementing regular expression), and you may end up in state 2a/2b (which becomes non-terminal state in the complementing regular expression).
Problem
There's a question on my exercise sheet to find the complement of two formulas (1) `(aa|bb)*` and (2) `(a|b)(aa|bb)(a|b)`. complement of both is in my opinion `a* | b*`, meaning only `a`'s or only `b`'s?