Основы трансляции - 14 стр.

   При построении распознавателей к вопросу о необходимости
преобразования КА в ДКА надо подходить, основываясь на принципе разумной
достаточности. Моделировать работу ДКА существенно проще, чем
произвольного КА, но при выполнении преобразования число состояний
автомата может существенно возрасти и в худшем случае составит     , где
- количество состояний исходного КА. В этом случае затраты на
моделирование ДКА окажутся больше, чем на моделирование исходного КА.

   1.7. Алгоритм построения минимального конечного автомата
   Многие КА можно минимизировать. Минимизация КА заключается в
построении эквивалентного КА с меньшим числом состояний. В процессе
минимизации необходимо построить автомат с минимально возможным числом
состояний, эквивалентный данному КА.
   Для минимизации автомата используется алгоритм построения
эквивалентных состояний КА.
   Определение: Два различных состояния в конечном автомате
M (Q; V; ±; q0; F) q 2 Q и q0 2 Q называются n -эквивалентными (n -
неразличимыми), n ¸ 0 n 2 N [ f0g, если, находясь в одном из этих состояний
и получив на вход любую цепочку символов !: ! 2 V ¤, j!j · n, автомат может
перейти в одно и то же множество состояний.
   Очевидно, что 0-эквивалентными состояниями автомата M (Q; V; ±; q0; F)
являются два множества его состояний: F и Q ¡ F .
   Определение: Множества эквивалентных состояний автомата называют
классами эквивалентности, а всю их совокупность - множеством классов
эквивалентности R (n), причем R (0) = fF; Q ¡ F g.
                 Алгоритм построения эквивалентных состояний
   Рассмотрим работу алгоритма построения эквивалентных состояний по
шагам:
   Шаг 1. n := 0, строим R (0).
   Шаг 2. n := n + 1, строим R (n) на основе R (n ¡ 1):
       R(n) = fri(n) : fqij 2 Q : 8a 2 V ± (qij ; a) µ rj (n ¡ 1)g 8i; j 2 Ng.
   То есть в классы эквивалентности на шаге n входят те состояния, которые по
одинаковым символам переходят в n ¡ 1 эквивалентные состояния.
   Шаг 3. Если R(n) = R (n ¡ 1), то работа алгоритма закончена, иначе
необходимо вернуться к шагу 2.
   Доказано, что алгоритм построения множества классов эквивалентности
завершится максимум для n = m ¡ 2, где m - общее количество состояний
автомата.
                     Алгоритм построения минимального КА:
   Шаг 1. Из автомата исключаются все недостижимые состояния.
   Шаг 2. Строятся классы эквивалентности автомата.


                                     14