Разработка компиляторов
Эквивалентность конечных автоматов
Определение. Два автомата и называются эквивалентными, если они распознают один и тот же язык над алфавитом .
Определение. Два состояния и называются эквивалентными, если верно, что . Очевидно, что если два состояния и эквивалентны, то состояния и также эквивалентны
Кроме того, так как в детерминированном конечном автомате переход
может возникнуть только для конечного состояния , то никакое заключительное состояние не может быть эквивалентно незаключительному состоянию. Таким образом, если мы предположим, что начальные состояния автоматов эквивалентны, то мы можем получить и другие пары эквивалентных состояний. Если в одну из таких пар попадет заключительное состояние вместе с незаключительным, то и неэквивалентны. Напишем алгоритм разбиения множества состояний на классы эквивалентности:
Добавить (q10, q20) в Список; Список = 0; /* Множество эквивалентных множеств */ for each (q in Q1+Q2) { Добавить {s} в Список; } while (есть пара (qi, qj), входящая в Список) { Удалить пару (qi, qj) из Списка; Пусть A и A' - такие множества, что ; if (A != A') { A = A + A'; for () { Добавить ( в Список; } } }
Таким образом, мы получим разбиение множества на множества эквивалентных состояний, если и - эквивалентны. Теперь осталось проверить, что никакое из этих множеств не содержит заключительное и незаключительное соcтояния. Если это верно, то автоматы эквивалентны.
