6
$\begingroup$

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?

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

1 Answer 1

7
$\begingroup$

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.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .