Язык всех строк, который имеет ровно 1 тройку b - PullRequest
Новая
       30

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

0 голосов
/ 30 ноября 2018

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

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

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

1 Ответ

0 голосов
/ 30 ноября 2018

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