Разработка компиляторов




Пример минимизации конечного автомата


Рассмотрим процесс минимизации автомата, представленного на слайде. Согласно алгоритму, вначале мы произведем удаление недостижимых состояний - в нашем примере состояние F очевидно недостижимо и потому не попадет в минимизированный автомат.

Затем мы произведем разбиение множества состояний автомата на классы эквивалентности. Укажем такую последовательность разбиений:

  1. E, ABCD
  2. E, ABC, D, так как (D,b) = E.
  3. E, AC, B, D, так как (B,b) = D.

Таким образом, состояния A и C неразличимы. Поэтому получаем следующий автомат:




Содержание  Назад  Вперед