Теория автоматов. - 4 стр.

       Сумма 0 считается четной. Это автомат Мура, т.е. его выходной сигнал
однозначно определяется состоянием, в которое автомат перешел, поэтому вы-
ходные сигналы приписаны прямо к состояниям. Этот же автомат можно пред-
ставить отмеченной таблицей переходов (табл.3 ).

                                         Таблица 3
                              Н        Ч
                              qн       qч
                     1        qч       qн
                     2        qн       qч
                     3        qч       qн

       Автомат называется частичным, если некоторые комбинации
“состояние– входной сигнал” не могут возникнуть в реальных условиях. При
этом в графе автомата появляются состояния, из которых определены выходы
не для всех входных сигнаов (т.е. присутствуют не все стрелки), а в таблицах
переходов и выходов (и в отмеченной таблице переходов) имеются
незаполненные клеточки.
       Для выполнения эквивалентных преобразований, как и для структурного
синтеза, необходимо доопределить частичный автомат. Переходы и выходы
обычно доопределяют, исходя из соображений удобства минимизации.

             ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ АВТОМАТОВ

      Два атомата называются эквивалентными, если они имеют одинаковые
входные и выходные алфавиты и на одинаковые входные слова выдают
одинаковые выходные слова.


                         Переход от автомата Мили
                      К эквивалентному автомату Мура

       Законы функционирования автоматов Мили и Мура отличаются функци-
ей выходов. Поскольку каждой паре ”состояние – входной сигнал” автомата
Мили может соответствовать свой выходной сигнал, а в автомате Мура
выходной сигнал приписываенся состоянию, то каждой паре qi x j автомата
Мили ставится в соответствие состояние синтезируемого автомата Мура b i j.
       Таким образом, каждой клеточке таблицы переходов автомата Мили бу-
дет соответствовать новое состояние автомата Мура. Кроме того, поскольку
первый выходной сигнал автомат выдаст, когда из начального состояния под
воздействием первого входного сигнала перейдет в какое-то состояние, которое
и определит первый выходной сигнал, то необходимо для автомата Мура ввести
также начальное состояние b0, которому может быть приписан любой допусти-
мый выходной сигнал. Поскольку функции переходов у автоматов Мили и Му-
ра одинаковы, каждому состоянию автомата Мили ставится в соответствие
класс изоморфных состояний автомата Мура. Технику установления соответст-
вий рассмотрим на примере.
       Пример. Возьмем ранее рассмотренный автомат Мили (см. табл. 1 и 2).
Перерисуем табл. 1, указав в клеточках i j состояния bij синтезируемого