418
правок
Изменения
→Пример
Теперь построим на его основе ДКА. Мы можем построить автомат <tex>A_n</tex>, который запоминает последние <tex>n</tex> входных символов. Следовательно, когда мы находимся с состоянии, соответствующему подстроке <tex>\sigma_1 \sigma_2 \dots \sigma_n</tex>, и читаем очередной символ <tex>\gamma</tex>, то мы переходим в состояние, которому уже будет соответствовать подстрока <tex>\sigma_2 \sigma_3 \dots \sigma_n \gamma</tex>. Однако, в случае <tex>\sigma_1 = \gamma = a</tex> автомат переходит в допускающее состояние, где в цикле может переходить на любому символу. Следует отметить, что такая стратегия строит ДКА c <tex>2^n + 1</tex> состояниями. Ниже представлен автомат <tex>A_3</tex>, который распознает язык <tex>L_3</tex>.
Покажем, что построенные таким образом автоматы будут минимальными.
* Каждые две попарно различных строки <tex>x</tex> и <tex>y</tex> длины <tex>n</tex> различимы. Чтобы доказать это, достаточно рассмотреть строку <tex>b^{i-1}a</tex>, где <tex>i : 1 \leqslant i \leqslant n</tex> {{---}} самая левая позиция символа, в которой начинают различаться строки <tex>x</tex> и <tex>y</tex>, и проверить, что ровно одна строка <tex>xb^{i-1}a</tex> или <tex>yb^{i-1}a</tex> принадлежит <tex>L_n</tex>.
* Каждая строка длины <tex>n</tex> не принадлежит <tex>L_n</tex> и, следовательно, различима от строки <tex>a^{n+1}</tex>, которая принадлежит <tex>L_n</tex>.
* Таким образом, <tex>2^n + 1</tex> строк в <tex>\Sigma^n \cup \{a^{n+1}\}</tex> являются попарно различимыми для <tex>L_n</tex>. Как следствие, <tex>2^n + 1</tex> {{---}} минимальное количество состояний для ДКА, который способен распознать язык <tex>L_n</tex>.
== См. также ==
