26
Содержание
Введение
Тема контрольной работы по дисциплине "Прикладная теория цифровых автоматов" - "Абстрактные цифровые автоматы".
Цель работы - ознакомится с основными понятиями абстрактных цифровых автоматов; типами абстрактных автоматов; способами задания абстрактных автоматов; связью между моделями Мили и Мура; эквивалентными автоматами и эквивалентными преобразованиями автоматов; минимизацией числа внутренних состояний автомата и алгоритмом Ауфенкампа-Хона.
Состояния
а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
А
a2
а3
х
х1
x2
Если абстрактный автомат частичный, то в клетке таблицы его переходов, находящейся, на пересечении строки, отмеченной входным сигналом и столбца отмеченного соответствующим состоянием (при условии, что переход в это состояние под действием данного входного сигнала не определен) ставится прочерк, и любое входное слово, приводящее к указанному переходу является запрещенным.
Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.
Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом Xj, и столбца, отмеченного состоянием ак, ставится выходной сигнал Уm, который автомат выдает, находясь в состоянии аk при наличии входного сигнала Xj, что определяется выражением Ym= (аk, хj).
Страницы: 1, 2, 3, 4