What is the regex for the complement of $r = b^*(ab + a^* + abb(b^+))^*$ ?

I am thinking $(a+b)^*(abb)^+a^* $ since anything that contains $abb$ and is not followed by $b$'s would not be accepted by $r$. Would this be correct?

  • $\begingroup$ The word $abbab$ doesn't seem to be matched by either the original regular expression or its proposed complement. $\endgroup$ – Mark Dickinson Mar 3 '15 at 17:57

I think you're correct. The language produced by $r$ contains all words, $x$, such that for all instances of substring $abb$ in $x$, this substring is followed by at least one $b$. The complement of this language contains all words, $y$, that have at least one occurrence of $abb$ as a substring and it is not followed by $b$. So, yes the complement you found is correct (if I'm not mistaken, haha!).

But in the general case, the safest way to find the regex that produces the complement of the language of another regex is:

  • Construct the corresponding NFA
  • Create its equivalent DFA
  • Take DFA's complement (change accepting states to non-accepting and vice versa)
  • Derive the corresponding regex from the DFA of the previous step.

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.