Эквивалентность состояний ДКА — различия между версиями
(→Эквивалентность автоматов) |
|||
Строка 1: | Строка 1: | ||
+ | [[Категория: Теория формальных языков]] | ||
== Эквивалентность автоматов == | == Эквивалентность автоматов == | ||
Версия 23:06, 30 сентября 2010
Эквивалентность автоматов
- Определение: Два автомата и называются эквивалентными, если они распознают один и тот же язык над алфавитом .
- Определение: Два состояния и называются эквивалентными , если верно, что . Из этого следует, что если два состояния и эквивалентны, то и состояния и будут эквивалентными для . Кроме того, т.к. переход может возникнуть только для конечного состояния , то никакое допускающее(терминальное) состояние не может быть эквивалентно не допускающему состоянию. Нахождение классов эквивалентных состояний внутри автомата и их совмещение в одно состояние используется в быстром алгоритме Хопкрофта для минимизации автомата, работающий за .
- Определение: Слово различает два состояния , если . Также, если слово различает состояния и такие, что и , то слово различает состояния и . Нахождение пар различных состояний в автомате используется в алгоритме минимизации автомата, работающий за .