Минимизация числа внутренних состояний автомата

Минимизация заключается в исключении лишних состояний автомата и основана на разделении состояний на эквивалентные. Состояния называются эквивалентными, если при установке автомата в эти состояния они не обнаруживают разницы в поведении (при подаче одних и тех же входных букв на выходе одни и те же буквы). Минимизация состоит в последовательном разбиении состояний на классы по числу букв, на которые автомат одинаково реагирует. Затем каждую группу обозначают новым состоянием и перестраивают таблицу переходов. Выделяем первый эквивалентный класс. Разобьем состояния на группы в соответствии с одинаковым выходным состоянием. Затем рассматриваем переходы автомата под воздействием входных букв и выделяем одинаковые группы. Минимизацию проводим до тех пор, пока группы не перестанут расщепляться.

0 1 8 9 0 2 4 5 13 0 6 7 10 12 0 3 11 14

1 1 9 11 1 - - - - 1 - - - - - 1 13 - -

0 1 8 9 0 2 4 5 13 0 6 7 10 12 0 11 14 3 11 14

1 1 9 11 1 - - - - 1 - - - - - 1 - - 13 - -

0 1 8 9 0 2 4 5 13 0 6 7 10 12 0 11 14 3 11 14

1 1 9 11 1 - - - - 1 - - - - - 1 13 - 13 - -

0 1 8 9 0 2 4 5 13 0 6 7 10 12 0 11 14 3 11 14

8 6 - 10 8 3 - - - - 8 - - - - - 8 - - - 8 - - -

1 8 9 0 4 5 13 2 4 5 13 0 6 7 10 12 0 11 14 3 11 14

6 - 10 8 - - - - 3 - - - - 8 - - - - 8 - - - 8 - - -

1 9 11 1 - - - - 1 - - - - - 1 13 - 13 - -

1 8 9 0 4 5 13 2 4 5 13 0 6 7 10 12 0 11 14 3 11 14

2 - 9 3 - - - - - - - 3 - - - - 3 - - - - -

1 8 9 0 4 5 13 2 4 5 13 0 6 7 10 12 0 11 14 3 11 14

14 - 5 - 5 11 10 2 5 11 10 - 7 14 12 13 - 12 11 4 12 11

1 8 9 0 4 0 5 013 2 4 0 6 10 0 7 0 12 0 11 0 14 3

14 - 5 - 5 - 11 - 10 2 5 - 7 12 - 14 - 13 - 12 - 11 4

1 8 9 0 4 0 5 013 2 0 6 0 10 0 7 0 12 0 11 0 14 3

14 - 5 - 5 - 11 - 10 2 - 7 - 12 - 14 - 13 - 12 - 11 4

2 - 9 3 - 3 - 3 - - 3 - 3 - 3 - 3 - 3 - 3 - -

6 - 10 8 - 8 - 8 - 3 8 - 8 - 8 - 8 - 8 - 8 - -

1 9 11 1 - 1 - 1 - - 1 - 1 - 1 - 1 - 1 - 1 - 13

Полученные группы больнее не расщепляются. Найдены эквивалентные классы. Далее проводим перекодирование.