73
правки
Изменения
м
* С помощью данной конструкции можно Заметим, что если <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>.
→Разность ДКА
=== Разность ДКА ===
[[Файл:Multi_DKA_division.png]]
Рассмотрим автомат <tex>\overline{M} = \langle \Sigma , Q , s , Q \setminus T , \delta \rangle </tex>, то есть автомат <tex>M</tex>, в котором терминальные и нетерминальные состояния инвертированы. Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>M</tex>, а значит, задаёт язык <tex>\overline{M}</tex>. Таким образом, <tex>\overline{M}</tex> {{---}} регулярный.
