Скачать

Абстрактные цифровые автоматы

Тема контрольной работы по дисциплине "Прикладная теория цифровых автоматов" - "Абстрактные цифровые автоматы".

Цель работы - ознакомится с основными понятиями абстрактных цифровых автоматов; типами абстрактных автоматов; способами задания абстрактных автоматов; связью между моделями Мили и Мура; эквивалентными автоматами и эквивалентными преобразованиями автоматов; минимизацией числа внутренних состояний автомата и алгоритмом Ауфенкампа-Хона.

Цифровой автомат можно трактовать как устройство, осуществляющее прием, хранение и преобразование дискретной информации по некоторому алгоритму. С определенной точки зрения к автоматам можно отнести как реальные устройства (ЭВМ), так и абстрактные системы (математические модели).

Автоматом называется дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы.

Общая теория автоматов подразделяется на абстрактную и структурную.

Абстрактная теория автоматов, отвлекаясь от структуры автомата (т.е. не интересуясь способом его построения), изучает лишь поведение автомата относительно внешней среды. Абстрактная теория автоматов близка к теории алгоритмов, являясь по существу ее дальнейшей реализацией.

В противоположность абстрактной теории автоматов, структурная теория автоматов интересуется как структурой самого автомата, так и структурой входных воздействий и реакций автомата на них. В структурной теории изучаются способы построения автоматов, способы кодирования входных воздействий и реакций автомата на них. Структурная теория автоматов является продолжением и развитием абстрактной теории. Опираясь на аппарат булевых функций и на абстрактную теорию автоматов, структурная теория дает эффективные рекомендации по разработке реальных устройств вычислительной техники.

Абстрактный цифровой автомат (ЦА) является математической моделью дискретного управляющего устройства.

Абстрактный ЦА определяется множеством, состоящим из шести элементов:

S={ X,A,Y,,a_o},

где:

X={x₁, x₂,. x_n} - множество входных сигналов (входной алфавит);

Y={y₁, y₂, y_m} - множество выходных сигналов (выходной алфавит);

А={ a₀,a₁, a₂,. а_N} - множество состояний (алфавит состояний);

а_о - начальное состояние (а_оА);

 - функция переходов автомата, задающая отображение (ХхА) А, т.е. ставящая в соответствие любой паре элементов декартового произведения (ХхА) элемент множества А;

 - функция выходов автомата, задающая либо отображение (XxA) Y, либо отображение AY.

Иными словами, функция переходов  показывает, что автомат S, находясь в некотором состоянии а_jА, при появлении входного сигнала х_jХ переходит в некоторое состояние а_рА. Это можно записать:

a_p= (a_i,X_j).

Функция выходов  показывает, что автомат S, находясь в некотором состоянии а_jА, при появлении входного сигнала х_jХ выдает выходной сигнал у_kY. Это можно записать: у_k = (a_i, X_j).

Понятие состояние в определение автомата было введено в связи с тем, что часто возникает необходимость в описании поведения систем, выходы которых зависят не только от состояния входов в данный момент времени, но и от некоторой предыстории, т.е. от сигналов, которые поступали на входы системы ранее. Состояние как раз и соответствует некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входов в данный момент времени.

Абстрактный автомат функционирует в дискретном автоматном времени t=0,1,2,. и переходы из состояния в состояние осуществляются мгновенно. В каждый момент t дискретного времени автомат находится в определенном состоянии a (t) из множества А состояний автомата, причем в начальный момент времени t=0 он всегда находится в начальном состоянии а_о. В момент времени t, будучи в состоянии a (t), автомат способен воспринять на входном канале сигнал х (t)  X, и выдать на выходном канале сигнал y (t) = (a (t), x (t)), переходя в состояние a (t+1) = = (a (t),x (t)). Зависимость выходного сигнала от входного и от состояния означает, что в его составе имеется память.

По способу формирования функции выходов выделяют три типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат. Автомат Мили характеризуется системой уравнений:

y (t) = (a (t), x (t));

a (t+1) = δ (a (t), x (t)). (1-1)

Автомат Мура - системой уравнений:

y (t) = (a (t));

a (t+1) = δ (a (t), x (t)). (1-2)

С-автомат - системой уравнений:

у= y₁y₂

y₁ (t) = (a (t),x (t));

У₂ (t) = ₂ (a (t));

a (t+1) =δ (a (t),x (t)).

Произвольный абстрактный автомат Мили или Мура (рис.1.1.) имеет один входной и один выходной каналы. Произвольный абстрактный С-автомат имеет один входной и два выходны х канала (рис.1.2.).

Рисунок 1.1 - Абстрактный автомат

Рисунок.1.2 Абстрактный С-автомат

Если на вход абстрактного автомата Мили или Мура, установленного в начальное состояние а_о, подавать буква за буквой некоторую последовательность букв входного алфавита х (0), х (1),. - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у (0), у (1),. - выходное слово. Для случая С-автомата на его выходах будут появляться две последовательности: y₁ (0), y₁ (1),. и y₂ (0), y₂ (1),. В абстрактном С - автомате выходной сигнал y₂ (t) = (a (t)) выдается все время, пока автомат находится в состоянии a (t). Выходной сигнал y₁ (t) =λ₁ (a (t),x (t)) выдается во время действия входного сигнала x (t) при нахождении С-автомата в состоянии a (t).

Таким образом, на уровне абстрактной теории функционирование цифрового автомата понимается как преобразование входных слов в выходные слова.

Выделяют полностью определенные и частичные автоматы.

Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены для всех пар переходов (x_i,a_j).

Частичным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар переходов (x_i,a_j).

Абстрактный цифровой автомат называется инициальным, если на множестве его состояний А выделяется начальное состояние а_о.

Чтобы задать конечный автомат S, необходимо описать все элементы множества: S={ X,A,Y,,,a_o}. Существует несколько способов задания работы автомата, но наиболее часто используется табличный (матричный), графический, аналитический.

При табличном способе автомат задается двумя таблицами: таблицей переходов и таблицей выходов, или матрицей соединений. Таблица переходов произвольного полностью определенного автомата строится следующим образом: строки таблицы помечаютсябуквами входного алфавита автомата, а столбцы таблицы - буквами алфавита состояний автомата; В клетке таблицы переходов, находящейся напересечении строки, отмеченной входным сигналом x_i, и столбца отмеченного состоянием a_j, ставится состояние а_k, являющееся результатом перехода автомата из состояния a_j под воздействием входного сигнала х_i, что определяется выражением a_k= (a_j, х_j).

Таблица 1.1 Таблица переходов автомата