Search code examples
stringautomationregular-languagefinite-automata

Language of all strings that has exactly 1 triple b


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.


Solution

  • 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))