Finding the complement of a regular expression (a|b)*ab(a|b)*

There's a question on my exercise sheet to find the complement of r = (a|b)*ab(a|b)*

I've come up with 开发者_如何转开发a solution, but I'm not sure if it's correct. Please help me to check, and correct my errors.

I'm assuming that a and b are the only allowed symbols.

Your original expression matches any string that contains ab. The complement is any string that does not contain ab. In other words if there is an a the next character must be another a or the end of the string. If a b occurs it must be before all as.

So that gives the result:

b*a*

I think your expression is equivalent to this.

The given RE states the language having substring ab at least once The complement of the same would be ..language accepting no substring ab

Hence b*a* is the correct answer