3
$\begingroup$

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:

  1. $a^* \to (a^*(b+c))^+$.
  2. $(a+b) \to (\epsilon+(c(a+b+c)^*))$.
  3. $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?

$\endgroup$
  • 1
    $\begingroup$ @D.W. the question doesn't make it clear, but my understanding, which I also want my own question to have is this: generate a regexp $r'$, such that $\overline{L[r]} = L[r']$. In other words, if the word from $L$ is not matched by $r$, then it is in the language I need to define. I chose to define it by means of specifying a regular expression for it, because a regexp would accept only one language. But if this task is too hard, then maybe there is an alternative (but close enough) way of doing it, say, by translating a regex into DFA, modifying the DFA and then creating a regex from it. $\endgroup$ – wvxvw Sep 9 '15 at 9:21
  • 1
    $\begingroup$ "should I perhaps" -- yes, definitely! All constructions in the pipeline Regular Expression --> NFA --> DFA --> Inverted DFA are probably available from lecture/literature, hence you have to write down little and prove nothing. That's why the exercise is marked easy. $\endgroup$ – Raphael Sep 9 '15 at 10:12
  • $\begingroup$ @Raphael ok, thanks for encouragement. I'll try and see where I'm getting with it! $\endgroup$ – wvxvw Sep 9 '15 at 10:16
5
$\begingroup$

The problem with your attempt is that you've only looked at what happens when the regexp to transform is a simple one. For example, you've looked at what the complement of $a^*$ looks at. But in order to write a compositional complementation algorithm, you need to figure out how to compute a regular expression that recognizes the complement of the language of $r^*$, for an arbitrary regular expression $r$.

The bad news is that your approach to build a complement for $a^*$ does not generalize easily. Consider for example the regular expression $(a + b + c)$. A regular expression that recognizes its complement language is $\epsilon + (a + b + c) (a + b + c) (a + b + c)^*$ — but this isn't really useful to know if you're looking for the complement of $(a + b + c)^*$, which is the empty language. You can't reach the complement of $(a+b+c)^*$ from starring something related to the complement of $(a+b+c)$.

You can approach this problem by adding a complement operator to regular expressions, in which case the algorithm you're looking for is an algorithm to remove the complement operator from such generalized regular expressions. It turns out that this brings you close to an open problem, the generalized star height problem: it's unknown whether you can eliminate nested stars in such generalized regular expressions, which shows that the interaction between the star operator and the complement operator is poorly understood.

Your idea of transforming the regular expression into a DFA and back is a good one. It's perfectly reasonable a different representation of an object where the operation you're interested in is easier. In fact, this is the usual algorithm to find a regular expression for the complement language of a regular expression:

  1. Build a DFA that recognizes the language of the regular expression.
  2. Transform the DFA into one that recognizes the complement language.
  3. Build a regular expression whose language is that of the second DFA.

Step 2 is very easy: just swap accepting and non-accepting states. Note that this doesn't work on an NFA!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.