Изменения
Нет описания правки
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
== Проверка ДКА на эквивалентность ==
Заданы два автомата: <tex> \mathcal{A}_1 </tex> со стартовым состоянием <tex> s_1 </tex> и <tex> \mathcal{A}_2 </tex> со стартовым состоянием <tex> s_2 </tex> соответственно. Нужно проверить их на эквивалентность.
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними:<br>
Осталось лишь проверить в полученном автомате состояния <tex> s_1 </tex> и <tex> s_2 </tex> на эквивалентность. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>.
