![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Автоматы могут быть заданы следующими способами:
1. В виде графа
РИС. 5.1. Автомат Мили
РИС. 5.2. Автомат Мура.
При построении автомата Мили каждая дуга, соединяющая вершины и
, имеет обозначение
. Это означает следующее: находясь, в состоянии
автомат, отрабатывая входной сигнал
, выдает выходной сигнал
и переходит в состояние
.
Так как в автомате Мура выходной сигнал зависит только от текущего состояния
, то каждая дуга, соединяющая вершины
и
, имеет обозначение
.
2. В виде таблиц перехода и выхода (автомат Мили); отмеченной таблицы перехода (автомат Мура).
Автомат Мили описывается с помощью двух таблиц: таблицы перехода и таблицы выхода:
Таблица переходов (ТП) Таблица выходов (ТВ)
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
Автомат Мура описывается с помощью отмеченной таблицы перехода:
Таблица переходов (ТП)
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
ПРИМЕР.
Синтезировать автомат, на вход которого подаются монеты номинальной стоимостью 1, 2 и 3 копейки, а на выходе автомат выдает билет, если сумма набранных монет составляет 3 копейки, если сумма меньше 3 копеек, то автомат ничего не выдает, если сумма больше 3 копеек, то автомат возвращает деньги.
Определим входной, выходной алфавиты и множество внутренних состояний:
· входной алфавит - монеты номинальной стоимостью 1, 2 и 3 копейки
· выходной алфавит - на выходе возможны выходные символы:
- ничего;
- билет;
- возврат.
· множество внутренних состояний ,
где - начальное состояние автомата «в автомате ничего нет»;
- «в автомате 1 копейка»;
- «в автомате 1 копейка»;
- «в автомате 2 копейки»;
- «в автомате 3 копейки».
Граф автомата имеет вид:
РИС. 5.3. Автомат Мили
Таблицы перехода и выхода представлены в виде:
Таблица переходов (ТП) Таблица выходов (ТВ)
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |||
![]() | ![]() | ![]() | ![]() | Н | Н | Б | Н | |||
![]() | ![]() | ![]() | ![]() | Н | Б | В | Н | |||
![]() | ![]() | ![]() | ![]() | Б | В | В | Б |
Неопределенным состоянием называется несуществующее состояние.
Частичным автоматом называется автомат, в котором некоторые состояния в таблице перехода не определены. Для дальнейшего исследования неопределенное состояние некоторым образом доопределяют.
Дата публикования: 2014-11-03; Прочитано: 316 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!