Контрольная работа: Абстрактные цифровые автоматы
Пример заполнения таблицы выходов некоторого абстрактного полностью определенного автомата с входным алфавитом 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
| А | a1 | a2 | a3 |
| у | y1 | y2 | y2 |
Очевидно, абстрактный полностью определенный С-автомат задается двумя таблицами выходов, первая из которых есть таблица выходов автомата Мили, а вторая - Мура. Если автомат частичный, то в некоторых клетках его таблицы может стоять прочерк, что означает отсутствие выходного сигнала.
На практике таблицы переходов и выходов часто совмещают в одну таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц переходов представлены в табл.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.7
|
A X | a1 |
a2 |
a3 |
|
x1 | a2 /y2 | a3 /y3 | a1 /у3 |
|
x2 | a1 /у3 | a1 /y1 | a2 /y2 |
Таблица 1.8
|
Y |
y1 |
y2 |
y3 |
|
К-во Просмотров: 333
Бесплатно скачать Контрольная работа: Абстрактные цифровые автоматы
|