Контрольная работа: Абстрактные цифровые автоматы
Таблица 1.1 Таблица переходов автомата
Состояния |
а1
|
а2
|
… |
аk
|
входные сигналы |
x1
|
(a1,x1)
|
(a2, x1)
|
. |
(ак, x1)
|
… |
|
|
|
|
хj
|
(a1, хj)
|
(a2, хj)
|
… |
(ак, хj)
|
Пример заполнения таблицы переходов некоторого абстрактного полностью
определенного автомата с входным алфавитом X={х1,
х2} - и алфавитом состояний A={a1, a2, а3}
представлен в табл.1.2.
Таблица 1.2
А |
а1
|
a2
|
а3
|
х |
х1
|
а2
|
а3
|
а1
|
x2
|
а1
|
а1
|
a2
|
Если абстрактный автомат частичный, то в клетке таблицы его переходов,
находящейся, на пересечении строки, отмеченной входным сигналом и столбца отмеченного
соответствующим состоянием (при условии, что переход в это состояние под действием
данного входного сигнала не определен) ставится прочерк, и любое входное слово,
приводящее к указанному переходу является запрещенным.
Заполнение остальных клеток аналогично случаю полностью определенного
автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат
Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.
Таблица выходов полностью определенного автомата Мили строится
следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют
таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся
на пересечении строки, отмеченной входным сигналом Xj,
и столбца, отмеченного состоянием ак, ставится выходной сигнал Уm, который автомат выдает, находясь в состоянии аk при наличии входного сигнала Xj, что определяется выражением Ym= (аk,
хj).
Таблица 1.3 Таблица выходов абстрактного автомата Мили.
Состояния |
a1
|
a2
|
|
ak
|
Входные сигналы |
х1
|
(a1,x1)
|
(a2, x1)
|
|
(ak, x1)
|
… |
|
…. |
. |
|
хj
|
(a1,xj)
|
(a2, xj)
|
|
(aк, xj)
|
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |