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

   Шаг 3. Классы эквивалентности состояний исходного КА становятся со-
стояниями результирующего минимизированного КА.
   Шаг 4. Функция переходов результирующего КА очевидным образом стро-
ится на основе функции переходов исходного КА.
   Для этого алгоритма доказано:
   - во-первых, что он строит минимизированный КА, эквивалентный
заданному;
   - во-вторых, что он строит КА с минимально возможным числом состояний
(минимальный КА).
   Пример построения минимального конечного автомата
   Задан конечный автомат
                  M (fA; B; C; D; E; F; Gg ; f0; 1g ; ±; A; fD; Eg),
   где    ± (A; 0) = fBg,    ± (A; 1) = fCg,     ± (B; 1) = fDg,     ± (C; 1) = fEg,
± (D; 0) = fCg, ± (D; 1) = fEg, ± (E; 0) = fBg, ± (E; 1) = fDg, ± (F; 0) = fDg,
± (F; 1) = fGg, ± (G; 0) = fF g, ± (G; 1) = fEg.
   Граф переходов этого автомата приведен на рис. 4. Необходимо построить
эквивалентный ему минимальный КА.




             Рис 4. Граф переходов конечного автомата до его минимизации
   Шаг 1. Состояния F и G являются недостижимыми, они будут исключены
на первом шаге алгоритма.
   Шаг 2.Построим классы эквивалентности автомата:
   R(0) = ffA; B; Cg ; fD; Egg, n = 0;
   R(1) = ffAg ; fB; Cg ; fD; Egg, n = 1;
   R(2) = ffAg ; fB; Cg ; fD; Egg, n = 2.
   Шаг 3. Классы эквивалентности состояний исходного КА становятся со-
стояниями результирующего минимизированного КА:
                     A = fAg, BC = fBCg, DE = fDEg.
   Шаг 4. Построим минимальный конечный автомат:
                     M 0 (fA; BC; DEg ; f0; 1g ; ±0; A; fDEg),
   где ±0 (A; 0) = fBCg, ±0 (A; 1) = fBCg, ±0 (BC; 1) = fDEg,
       ±0 (DE; 0) = fBCg, ±0 (DE; 1) = fDEg.
   Граф переходов минимального КА приведен на рис. 5.


                                         15