73
правки
Изменения
м
→Применение
== Применение ==
Изменив конструкцию, можно получить автомат , допускающий разность или объединение двух языков.
=== Объединение ДКА ===
[[Файл:Multi_DKA_united.png]]
Необходимо разрешать любую цепочку , удовлетворяющую первому или второму автомату, для этого пометим сделаем терминальными следующие вершины <tex>T = (T_1 \times Q_2) \cup (Q_1 \times T_2)</tex>. Полученный автомат удовлетворяет нашим требованиям , так как попав в какое-либо состояние из <tex>T_1</tex> или <tex>T_2</tex>, цепочка начинает будет удовлетворять первому или второму автомату соответственно.
=== Разность ДКА ===
Заметим, что если <tex>L</tex> и <tex>M</tex> - регулярные языки, то <tex>L \setminus M = L \cap \overline{M}</tex> - так же регулярный.
Таким образом , надо построить пересечение двух автоматов, предварительно инвертировав во втором терминальные и нетерминальные состояния. Заметим, что меняется только набор терминальных вершин, следовательно заменим их в итоговой конструкции произведения ДКА на сделаем терминальными следующие вершины <tex>T = T_1 \times (Q_2 \setminus T_2)</tex>.
