Язык всех строк, который имеет ровно 1 тройку b

Я новичок в автоматах и ​​учусь составлять регулярные выражения для языков. Но я застрял на этом.

Предположим, у нас есть язык L, язык всех строк, который имеет ровно 1 тройку "b", определенную над набором алфавитов Σ = {a, b}
Теперь, после нескольких пытается, я придумал это
(a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )* но потом я понимаю, что это также неверно, потому что строка abbbabababb здесь не подходит.

Пожалуйста, укажите на мою ошибку или помогите мне решить ее, так как я потратил на это почти час.


string automation regular-language finite-automata
person Tom    schedule 29.11.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Начните с 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

(Пример DFA в действии)

Оттуда вы можете преобразовать DFA в регулярное выражение, хотя при использовании этого алгоритма состояние x 'dump' будет опущено. Вы получите что-то вроде выражения

(|a|ba|bba)*(bbb|bbba(|a|ba|bba)*(|b|bb))
person Welbog    schedule 30.11.2018