Изменения

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

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

17 байт убрано, 15:37, 15 января 2013
Проверка ДКА на эквивалентность
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними:<br>
[[Файл:auto_equiq.png|470px]]<br>
Осталось лишь проверить в полученном автомате состояния <tex> s_1 </tex> и <tex> s_2 </tex> на эквивалентность. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>. Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния автомата на классы эквивалентности.
172
правки

Навигация