Специальная математика. Соловьев А.Е. - 42 стр.

сказано, лишь математические модели, преобразующие входные слова в выходные и не
имеющие дела с физическими сущностями, вроде монет, билетов и т.п.
Пример 1 (автомат Мили):
Построить (синтезировать) автомат, на вход которого могут поступать в любой
последовательности и, возможно, с повторениями монеты (как в добрые старые времена) 1;
2 и 3 копейки. Автомат продает билет, если сумма опущенных монет равна 3. В случае
превышения суммы автомат возвращает деньги.
Входной алфавит в описании задан явно: Х = {1, 2, 3}.
Выходной алфавит будет содержать буквы (сигналы): Б – выдает билет, В – возвращает
деньги, Н – ничего не выдает (это такой специфический выходной сигнал). То есть У = {Б,
В, Н}.
Можно представить автомат в виде графа, где вершины представляют состояния, а к каждой
стрелке приписана пара входной сигнал/выходной сигнал. То есть размеченные стрелки
отражают функции переходов и выходов.

                                q1


              3/В         1/Н                    1/Н

                            2/Б           1/Н

                     2/Н
                                                             q2
         q0
                    3/Б                    1/Б         2/Н

          2/В         3/Б
                                     q3



От представления автомата в виде графа можно очевидным образом перейти к его
табличному представлению, которое также однозначно определяет автомат. Табличное
представление предпочтительно для автоматов с большим числом состояний и при
представлении автоматов в компьютере.

Можно построить для данного автомата таблицы
переходов
Т.П. q0 q1 q2 q3
1 f q1 q2 q3 q1
2    q2 q3 q0 q2
3    q3 q0 q0 q3
и

выходов
Т.В. q0 q1 q2 q3
1    Н Н Б Н
  
2    Н   Б    В      Н
3    Б   В    В      Б


                                                       — 42 —