Search for a regular expression add-on

Question

alt text http://img31.imageshack.us/img31/4383/image24xu.jpg

My exercise sheet has a question about finding the complement r = (a|b)*ab(a|b)*

I came up with a solution, but am not sure if it is right. Please help me verify and correct my errors.

Answer 1

I assume that a and b are the only valid characters.

Your original expression matches any string containing ab . A complement is any string that does not contain ab . In other words, if a exists, the next character must be another a or the end of the string. If a b occurs, it must be up to all a s.

So this gives the result:

 b*a* 

I think your expression is equivalent to this.

Answer 2

This RE indicates a language that has the substring ab at least once. In addition to that, it would be ... a language that does not accept the substring ab

Therefore b * a * is the correct answer