I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.
Suppose we have a language L, Language of all strings that has exactly 1 triple “b” defined over alphabet set Σ = {a, b}
Now after several tries, I came up with this
(a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )*
but then I realize that this is wrong too because the string abbbabababb doesn't fit on this.
Kindly someone point out at my mistake or help me solve it as I have spent almost an hour on this.
Start with a DFA that describes the language:
States: start, b, bb, bbb, bbba, bbbab, bbbabb, x
Accepting: bbb, bbba, bbbab, bbbabb
Transitions:
start, a, start
start, b, b
b, a, start
b, b, bb
bb, a, start
bb, b, bbb
bbb, a, bbba
bbb, b, x
bbba, a, bbba
bbba, b, bbbab
bbbab, a, bbba
bbbab, b, bbbabb
bbbabb, a, bbba
bbbabb, b, x
(Example of this DFA in action)
From there, you can convert the DFA into a regular expression, though you'll omit the x 'dump' state when using this algorithm. You'll end up with an expression something like
(|a|ba|bba)*(bbb|bbba(|a|ba|bba)*(|b|bb))