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

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Рубрика: 

Примеры.1. Построить (синтезировать) автомат, на вход которого могут
поступать в любой последовательности и, возможно, с любым числом повторе-
ний монеты 1,2 и 3 коп. Автомат продает билет, если сумма опущенных монет
равна 3. В случае превышения суммы автомат возвращает деньги.
Входной алфавит в описании задан явно: X={1,2,3}.
Выходной алфавит будет содержать буквы (сигналы): Б- выдает билет,
В- возвращает деньги, Н- ничего не выдает, т.е. Y{Н,Б,В}.
Внутренние состояние будем отождествлять с суммой, которую помнит
автомат. Будем иметь в виду, что после продажи билета или возврата денег
автомат помнит нулевую сумму: Q={q
0
, q
1
, q
2
}, здесь индекс соответствует сум-
ме.
Автомат в виде графа представлен на рис. 1
Рисунок 1
Это автомат Мили. Надпись 1/Б; 2,3/В у стрелки q
2
q
0
означает, что если в
состоянии q
2
будет принят сигнал 1, выходной сигнал будет Б, а для входных
сигналов 2 и 3 выходным будет В. Этот же автомат можно представить в виде
двух таблиц: таблицы переходов (табл.1) и таблицы выходов (табл.2)
Таблица 1 Таблица 2
2. Построить автомат, на вход которого могут поступать монеты 1, 2 и 3
коп. Автомат выдает сигнал “чет.” (Ч), если сумма опущенных монет четная, и
“нечет.” (Н), если нечетная (рис.2).
Рисунок 2.
q
0
q
1
q
2
1 q
1
q
2
q
0
2 q
2
q
0
q
0
3 q
0
q
0
q
0
q
0
q
1
q
2
1 Н Н Б
2 Н Б В
3 Б В В 
       Примеры.1. Построить (синтезировать) автомат, на вход которого могут
поступать в любой последовательности и, возможно, с любым числом повторе-
ний монеты 1,2 и 3 коп. Автомат продает билет, если сумма опущенных монет
равна 3. В случае превышения суммы автомат возвращает деньги.
       Входной алфавит в описании задан явно: X={1,2,3}.
       Выходной алфавит будет содержать буквы (сигналы): Б- выдает билет,
В- возвращает деньги, Н- ничего не выдает, т.е. Y{Н,Б,В}.
       Внутренние состояние будем отождествлять с суммой, которую помнит
автомат. Будем иметь в виду, что после продажи билета или возврата денег
автомат помнит нулевую сумму: Q={q0, q1, q2}, здесь индекс соответствует сум-
ме.
       Автомат в виде графа представлен на рис. 1
                                                       Рисунок 1




       Это автомат Мили. Надпись 1/Б; 2,3/В у стрелки q2q0 означает, что если в
состоянии q2 будет принят сигнал 1, выходной сигнал будет Б, а для входных
сигналов 2 и 3 выходным будет В. Этот же автомат можно представить в виде
двух таблиц: таблицы переходов (табл.1) и таблицы выходов (табл.2)

             Таблица 1                             Таблица 2

              q0    q1    q2                         q0    q1    q2
         1    q1    q2    q0                   1     Н     Н     Б
         2    q2    q0    q0                   2     Н     Б     В
         3    q0    q0    q0                   3     Б     В     В



       2. Построить автомат, на вход которого могут поступать монеты 1, 2 и 3
коп. Автомат выдает сигнал “чет.” (Ч), если сумма опущенных монет четная, и
“нечет.” (Н), если нечетная (рис.2).
                                               Рисунок 2.

Страницы