Функции 3 страница

Функцию выходов определим следующим образом. Если в автомате Мура δ_A(a_m, z_f) = a_s и λ _а(a_s) = w_g, то в автомате Мили

Переход от автомата Мура к автомату Мили при графическом способе их задания проиллюстрируем рисунком (см. рис. 26):

Рис. 26

Как следует из рисунка, выходной сигнал записанный рядом с вершиной переносится на все дуги, входящие в эту вершину.

Пример. Задан автомат Мура в виде графа (см. рис.27), построить эквивалентный ему автомат Мили (см. рис. 28).

Рис. 27

Рис. 28

При табличном способе задания автомата : таблица переходов совпадает с таблицей переходов автомата а таблица выходов получается из таблицы переходов заменой символа стоящего на пересечении строки и столбца символом выходного сигнала отмечающего столбец в таблице переходов автомата

Из самого способа построения автомата Мили очевидно, что он эквивалентен автомату Мура Действительно, если некоторый входной сигнал поступает на вход автомата находящегося в состоянии то он перейдёт в состояние и выдаст выходной сигнал Но соответствующий автомат Мили из состояния также перейдет в состояние поскольку и выдаст тот же выходной сигнал согласно способу построения функции Т.о., для входной последовательности длиной в одну букву, поведения автоматов полностью совпадают. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов установленных, в состояния вызовет появление одинаковых выходных слов и, следовательно, автоматы и эквивалентны.

Теперь рассмотрим трансформацию автомата Мили в автомат Мура, причем это преобразование будем выполнять для двух видов автомата Мили:

а) автомат Мили не содержит преходящих состояний;

б) автомат Мили имеет состояние являющееся переходящим.

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

Итак, пусть задан автомат Мили:

реализует отображение - отображение

- начальное состояние. Построим автомат Мура: у которого

Для определения Ав каждому состоянию поставим в соответствие множество всевозможных пар вида (см. рис. 29), где - выходной сигнал, приписанный входящей в дуге:

Рис. 29

Число элементов в множестве равно числу различных выходных сигналов на дугах автомата входящих в состояние

Множество состояний автомата получим как объединение множеств

Функции выходов и переходов определим следующим образом. Каждому состоянию автомата Мура представляющему собой пару вида поставим в соответствие выходной сигнал Если в автомате Мили был переход и при этом выдавался выходной сигнал то в будет переход из множества состояний порождаемых в состояние

под действием входного сигнала Проиллюстрируем переход от модели Мили к модели Мура с помощью рис. 30.

Рис. 30

В качестве начального состояния а_1в можно взять любое из состояний множества которое порождается начальным состоянием автомата Напомним, что при сравнении реакций автоматов и на всевозможные входные слова не должен учитываться выходной сигнал в момент t = 0, связанный с состоянием автомата

Пример. Выполнить преобразование автомата Мили заданного а виде графа (см. рис. 31), в автомат Мура

В автомате Мили:

определяются графом автомата.

В эквивалентном автомате Мура:

Построим множество для чего найдем множества пар, порождаемых каждым состоянием автомата обозначим их для краткости символами:

Рис. 31

С каждым состоянием, представляющим собой пару, отождествим выходной сигнал, являющийся вторым элементом этой пары:

Функция строится следующим образом. В автомате Sa из состояния есть переход под действием сигнала в состояние с выдачей следовательно, из множества состояний порождаемых в автомате (см. рис. 32) должен быть переход в состояние под действием сигнала Аналогично, из состояний должен быть переход в состояние под действием сигнала и т.д. В качестве начального состояния можно выбрать любое из

Рис. 32

Рассмотрим теперь второй вариант преобразования автомата Мили в автомат Мура, когда состояние у первого из них - преходящее (см. рис. 33).

Как и в предыдущем примере определяем число состояний автомата Мура:

Рис. 33

К множеству пар - состояний автомата Мура добавим состояние порождаемое преходящим состоянием a₁, считая, что выходной сигнал в состоянии не определен. Функцию переходов определим как в предыдущем примере, в частности из состояния будут переходы в под действием сигнала под действием Так как - начальное состояние автомата Мили, то в качестве начального состояния автомата Мура следует взять порождаемое им состояние Граф автомата Мура эквивалентный автомату Мили имеет вид, показанный на рис. 34.

Рис. 34

Эквивалентность автоматов S_a и S_b при преобразовании автомата Мили в автомат Мура на множестве входных слов конечной длины легко доказать по индукции подобно изложенному выше при обратном преобразовании.

Рассмотренные методы взаимной транспозиции моделей Мили и Мура показывают, что при переходе от

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

4.6. Минимизация полностью определенных автоматов Мили

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

Два состояния автомата и называются эквивалентными если для всевозможных входных слов Состояния и эквивалентны если для всевозможных входных слов длины

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

избыточные элементы в множестве состояний Если каждый класс эквивалентности содержит только одно состояние, множество несократимо. Если один или несколько классов содержат более одного элемента, то все элементы, кроме одного в каждом классе могут быть исключены из множества

Рассмотрим минимизацию числа состояний автомата Мили.

Пример. Задан автомат Мили таблицами переходов (табл. 12) и выходов (табл. 13). Необходимо минимизировать число его состояний.

По таблице выходов получаем разбиение на классы одноэквивалентных состояний, объединяя в эквивалентные классы одинаковые столбцы:

Строим таблицу -разбиения (табл. 14).

Строим таблицу разбиения (табл.15):

Аналогично строим разбиение (табл. 16):

Строим разбиение: Мы видим, что разбиение совпадает с разбиением, следовательно, процедура разбиения завершена. Разбиение есть разбиение множества состояний автомата Мили (исходного) на классы эквивалентных между собой состояний. Выбирая произвольно из каждого класса по одному состоянию, получим множество множество состояний минимального автомата Мили. Например, "Лишние" состояния удаляем из исходных таблиц переходов и выходов, при этом получаем таблицы переходов (табл. 17) и выходов (табл. 18) минимального автомата.

При минимизации полностью определенных автоматов Мура вводится понятие 0-эквивалентности состояний и рассматривается разбиение множества состояний на 0-классы. 0-эквивалентными называют любые одинаково отмеченные состояния автоматов Мура. Если два 0-эквивалентных состояния любым входным сигналом переводятся в два 0-эквивалентных состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автоматов Мура определяются аналогично приведенному выше алгоритму минимизации для автомата Мили.

Пример. Задан автомат Мура отмеченной таблице переходов (табл. 19). Необходимо минимизировать число его состояний.

Строим - разбиение (табл. 20):

Строим - разбиение (табл. 21):

Строим - разбиение:

В результате получаем отмеченную таблицу переходов минимального автомата Мура (табл. 22):

4.7. Структурный автомат

В отличие от абстрактного автомата, имеющего один вход и один выход, на которые поступают сигналы во входном и выходном алфавитах, структурный автомат имеет входные и выходные полюса (см. рис.35), на каждом из которых сигнал может принимать два значения: 0 или 1.

Рис. 35

Таким образом, входному сигналу абстрактного автомата соответствует некоторый вектор компонента, которого равна нулю или единице, т.е. входному сигналу на полюсе, а число компонент равно числу входных полюсов. Для представления (кодирования) входных сигналов абстрактного автомата различными векторами должно быть выполнено условие: - ближайшее большее целое число.

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

Закодируем входные и выходные сигналы абстрактного автомата, заданного таблицами 23 и 24.

Так как число входных сигналов этого автомата равно трем, а выходных - шести, в структурном автомате достаточно иметь два входных и три выходных полюса. Пусть, например, входным сигналам абстрактного автомата соответствуют коды:

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

На этапе структурного синтеза принято представлять автомат в виде двух частей: памяти и комбинационной схемы (см. рис 36)

Рис. 36

Память автомата состоит из предварительно выбранных элементов памяти - элементарных автоматов Мура Мы будем использовать один из самых простых и довольно распространенных элементов памяти — -триггер с двумя входами: информационным и синхронизирующим Условное изображение таблица работы -триггера имеют вид:

В D-триггере, как и во всех автоматах Мура, используемых в качестве элементов памяти, каждое состояние отмечено своим, отличным от других, выходным сигналом, что позволяет отождествлять его состояние и выходные сигналы. Другими словами, если триггер находится в состоянии 0 или 1, то с его выхода снимается сигнал 0 или 1 соответственно. Поэтому вместо отмеченной таблицы переходов используется для описания работы элементарного автомата просто таблицы переходов -триггеров. Вход С в этой таблице опущен, но имеется в виду, что изменение состояния -триггера возможно лишь при наличии единицы на входе С.