Search code examples
regular-language

Regular expressions for strings not containing specific substring

What could be the regular expression for - All words that do not have the substring baa for alphabet set ={a,b}?

Is it:

a* ((aa) * b *)?

Can a string of length 2 be acceptable for the above condition to hold?

Solution 
  • a*(ba?)*

    At start, it can go with arbitrarily many a's, but once a b has been introduced, not more than a single isolated a is allowed to appear anywhere hereupon.