恰好有 1 个三元组 b 的所有字符串的语言

Question

我是自动机新手，正在学习为语言制作正则表达式。但是我一直卡在这个上面。

假设我们有一种语言 L，所有字符串的语言恰好有 1 个三元组 “b” 在字母集 Σ = {a, b} 上定义
现在经过几次尝试，我想到了这个
(a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )* 但后来我意识到这也是错误的，因为字符串 abbbabababb 不适合这个。

请大家指出我的错误或帮助我解决问题，因为我为此花了将近一个小时。

Answer 1

从描述语言的 DFA 开始：

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)

从那里，您可以 convert the DFA into a regular expression，但在使用此算法时您将省略 x 'dump' 状态。您最终会得到类似

的表达式

(|a|ba|bba)*(bbb|bbba(|a|ba|bba)*(|b|bb))

恰好有 1 个三元组 b 的所有字符串的语言

Language of all strings that has exactly 1 triple b

string

automation

regular-language

finite-automata