Контрольная работа: Абстрактные цифровые автоматы
Пример заполнения таблицы выходов некоторого абстрактного полностью
определенного автомата с входным алфавитом X={x1, x2}, алфавитом
состояний A={a1, а2,
а3} и выходным алфавитом Y={y1, y2, y3}-представлен
в табл.1.4.
Таблица 1.4
a |
a1
|
a2
|
a3
|
x |
x1
|
у2
|
у3
|
y1
|
x2
|
y3
|
у1
|
у2
|
Таблица выходов полностью определенного автомата Мура строится
более просто: каждому состоянию автомата ставится в соответствие свой выходной сигнал.
Пример таблицы выходов автомата Мура с алфавитом состояний A={a1, а2, а3} и выходным алфавитом
Y={y1, y2,
у3} представлен в таблице 1.5.
Таблица 1.5
Очевидно, абстрактный полностью определенный С-автомат задается
двумя таблицами выходов, первая из которых есть таблица выходов автомата Мили, а
вторая - Мура. Если автомат частичный, то в некоторых клетках его таблицы может
стоять прочерк, что означает отсутствие выходного сигнала.
На практике таблицы переходов и выходов часто совмещают в одну
таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц
переходов представлены в табл.1.6. - 1.8 (Общий вид отмеченной таблицы переходов
- табл.1.6., отмеченная таблица переходов автомата Мили - табл.1.7., отмеченная
таблица переходов автомата Мура - табл.1.8.).
Кроме рассмотренных выше таблиц переходов и выходов произвольный
абстрактный автомат может быть задан матрицей соединений.
Матрица соединений является квадратной и содержит столько столбцов
(строк), сколько различных состояний содержит алфавит состояний данного автомата.
Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата.
В клетке, находящейся на пересечении столбца, помеченного буквой аj и строки, помеченной буквой as автомата, ставится входной
сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется
данный переход.
Для абстрактного автомата Мили в клетке рядом с состоянием проставляется
также выходной сигнал, который автомат выдает в результате данного перехода (табл.1.9.)
Для автомата Мура выходной сигнал проставляется в строке рядом с состоянием (эти
состояния соответствуют исходным состояниям автомата).
Таблица 1.6
Состояния |
a1
|
a2
|
… |
ak
|
Входные сигналы |
x1
|
(a1,x1))
|
(a2,x1)
|
… |
(ak,x1)
|
(a1,x1)
|
(a2,x1)
|
… |
(ak,x1)
|
… |
… |
… |
… |
… |
xj
|
(a1,xj)
|
(a2, xj)
|
… |
(аk, xj)
|
(a1,xj)
|
(a2, xj)
|
… |
(аk,
xj)
|
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |