CODEWITHSUNDEEP
regex
segfault
segfault

Reputation: 5939

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.

Upvotes: 4

Views: 4758

Answers (2)

Optimus
Optimus

Reputation: 11

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

Upvotes: 1

Mark Byers
Mark Byers

Reputation: 838186

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.

Upvotes: 6

Related Questions