CODEWITHSUNDEEP
regexregular-languagecomputation-theory
u_ser722345
u_ser722345

Reputation: 669

Is the language L={words without the substring 'bb' } regular?

L = {words such that the substring 'bb' is not present in in it

Given that the alphabet is A = {a,b}, is this language regular? If so, is there a regular expression that represents it?

Upvotes: 1

Views: 1381

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

Yes, this language is regular. Since this looks like homework, here's a hint: if the string bb isn't present, then the string consists of lots of blocks of strings of the form a* or a*b. Try seeing how to assemble the solution from this starting point.

EDIT: If this isn't a homework problem, here's one possible solution:

(a*(ba+)*b?)?

The idea is to decompose the string into a lot of long sequences of as with some b's interspersed in-between them. The first block of a's is at the front. Then, we repeatedly place down a b, at least one a, and then any number of additional as. Finally, we may optionally have one b at the end. As an alternative, we could have the empty string, so the entire thing is guarded by a ?.

Hope this helps!

Upvotes: 4

Related Questions