Я не могу создать DFA для этого языка - PullRequest
Новая
       22

Я не могу создать DFA для этого языка

2 голосов
/ 15 января 2020 
{w∈{a,b}∗|w has baba as a substring}

Я запутался с этим. Например, как я могу получить следующий ввод? 

aaababa
abbbaba
ababbba
ababaaaa

Кажется, что всегда должна быть баба либо в середине, либо в начале, либо в конце. Я должен решить, всегда ли ставить его в начале, середине или конце?

Спасибо

1 Ответ

3 голосов
/ 15 января 2020

По теореме Майхилла-Нероде состояния:

  • Уже соответствует 'baba' (состояние принятия)
  • Сразу после 'bab', и не соответствует ' Баба '
  • Сразу после' ба ', и не соответствует' Баба '
  • Сразу после' б ', и ничего из вышеперечисленного
  • Ничего из вышеперечисленного ( начальное состояние)

По сути, это тот же DFA, созданный алгоритмом поиска Кнута-Морриса-Пратта.

...