Абстрактная и структурная теории конечных автоматов. Структура операционного устройства. Способы задания автоматов, страница 7

3) В таблицах переходов и выходов вычёркиваются столбцы, соответствующие не вошедшим в множество  состояниям, а в оставшихся столбцах таблицы переходов  все состояния заменяются на эквивалентные из множества .

4) В качестве начального состояния  выбирается одно из состояний, эквивалентное а₀ . В частности, удобно за  выбирать само состояние а₀ .

Для примера, найдем минимальные таблицы переходов и выходов автомата S, изображённого на рис.1.6.

Рис.1.6    Таблицы переходов и выходов                                                            

1)  Находим разбиение p₁ множества состояний а₁,а₂,а₃,а₄,а₅,а₆,а₇,а₈ на одно-совместимые классы. По таблице выходов находим, что таких класса два:            В₁={a₁,a₂,a₃},        B₂={a₄,a₅,a₆,a₇,a₈}.

Подставим в таблицу переходов (рис.1.6) вместо состояний а₁¸а₈ соответствующие значения В₁, В₂. После подстановки получим таблицу, изображённую на  рис. 1.7.

                                           В₁                                                   В₂

Рис.1.7

б) Находим разбиение p₂ множества состояний а₁,а₂,а₃,а₄,а₅,а₆,а₇,а₈ на 2-совместимые  классы. Двух - совместимые классы находятся внутри одно-совместимых классов. Выделяют их по следующему общему правилу. Если в таблице переходов автомата, в котором состояния обозначены наименованиями l-совместимых классов, несколько столбцов, относящихся к одному и тому же классу, одинаковые, то состояния автомата, обозначающие эти столбцы, образуют l+1 - совместные состояния. В соответствии с этим правилом, по таблице (рис.1.7) находим 2-совместимые классы.  С₁={a₁,a₂} , C₂={a₃} , С₃={a₄,a₅} , C₄={a₆,a₇,a₈}.

С1           С2             С3                    С4   а1 а2 а3  а4  а5   а6 а7  а 8          z1 C1 C1 C4 C1 C1 C3 C4 C3       z2  C3 C3 C1 C4 C4 C2 C1 C1

Подставим в таблицу переходов (рис.1.6) вместо состояний а₁¸а₈ соответствующие значения С_1, С₂, С₃, С₄ . После подстановки получим таблицу, изображённую на рис.1.8.

Рис.1.8