Изменения

Перейти к: навигация, поиск

Эквивалентность состояний ДКА

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

Навигация