# Complement of a regular expression?

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?

• The word $abbab$ doesn't seem to be matched by either the original regular expression or its proposed complement. – 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!).