Disclamer: this is my uni assignment, which is rated comparatively low, thus I assume that the answer should be simple. Hints are appreciated (as opposed to direct answers).
Write an algorithm which accepts a regular expression $r$ and produces a language $\overline{L[r]}$.
I think it is reasonable to assume that all operations I need to consider are just the concatenation, union and Kleene star. For simplicity, I assumed the alphabet to be $\{a,b,c\}$. I also think that I can invert individual operations as follows:
- $a^* \to (a^*(b+c))^+$.
- $(a+b) \to (\epsilon+(c(a+b+c)^*))$.
- $ab \to \epsilon+((aa+b+c)(a+b+c)^*)$.
But attempting to combine these operations produces wrong results, for example:
$$ a^*b^* \to \\ (a^*(b+c))^+(b^*(a+c))^+ \to \\ (\epsilon+((a^*(b+c))^+(a^*(b+c))^++b+c)(a+b+c)^*)(\epsilon+((b^*(a+c))^++a+c)(a+b+c)^*)) $$
doesn't seem to do what I expect it to because, for example, it will match the empty string on both sides.
Should I perhaps consider transforming the regexp into DFA and "inverting" the DFA instead?