Разработка компиляторов
Пример минимизации конечного автомата
Рассмотрим процесс минимизации автомата, представленного на слайде. Согласно алгоритму, вначале мы произведем удаление недостижимых состояний - в нашем примере состояние F очевидно недостижимо и потому не попадет в минимизированный автомат.
Затем мы произведем разбиение множества состояний автомата на классы эквивалентности. Укажем такую последовательность разбиений:
- E, ABCD
- E, ABC, D, так как (D,b) = E.
- E, AC, B, D, так как (B,b) = D.
Таким образом, состояния A и C неразличимы. Поэтому получаем следующий автомат:
