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

       

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


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

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

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

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



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







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий