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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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: