2.4.2. Автомат Мили.: Автомат Мили отличается тем, что его функции выхода в момент t

Основные понятия теории абстрактных автоматов

2.4.2. Автомат Мили.: Автомат Мили отличается тем, что его функции выхода в момент t

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

“Теория автоматов” – является одной из важных компонент федерального государственного стандарта по направлению “Информатика и вычислительная техника”.

Теория автоматов имеет широкие возможности применения:

  • Проектирование систем логического управления;
  • Обработка текстов и построение компиляторов;
  • Спецификация и верификация систем взаимодействующих процессов;
  • Языки описания документов и объектно-ориентированных программ;
  • Оптимизация логических программ др.

Об этом можно судить по выступлениям на семинаре “Software 2000…” ученых и специалистов.

Дуг Росс: “…80 или даже 90 % информатики (Computer Science) будет в будущем основываться на теории конечных автоматов…”

Herver Gallaire: “Я знаю людей из “Боинга”, занимающихся системами стабилизации самолетов с использованием чистой теории автоматов. Даже трудно себе представить, что им удалось с помощью этой теории. “

Brian Randell : “Большая часть теории автоматов была успешно использована в системных программах и текстовых фильтрах в ОС UNIX. Это позволяет множеству людей работать на высоком уровне и разрабатывать очень эффективные программы”.

Простейший преобразователь информации (рис.1.1,а) отображает некоторое множество элементов информации Х, поступающее на вход, в некоторое множество на выходе Y.

Если множества Х и Y являются конечными и дискретными, то есть преобразование осуществляется в дискретные моменты времени, то такие преобразователи информации называются конечными преобразователями.

Элементы множеств Х и Y в этом случае предварительно кодируют двоичными кодами и строят преобразование одного множества в другое.

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

Рис. 1.1.

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

В этом случае говорят об автоматном преобразовании информации (рис.1.1,б). На один и тот же входной сигнал автомат может реагировать по-разному, в зависимости от состояния, в котором он находился. Автомат меняет свое состояние с каждым входным сигналом.

Рассмотрим несколько примеров.

Пример 11. Автомат, описывающий поведение “умного” отца.

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

Зададим такой автомат графом, в котором вершины соответствуют состояниям, а дуга из состояния s в состояние q, помеченное x/y, проводится тогда, когда автомат из состояния s под воздействием входного сигнала х переходит в состояние q с выходной реакцией y. Граф автомата, моделирующего умное поведение родителя, представлен на рис.1.2.

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

– брать ремень;

– ругать сына;

– успокаивать сына;

– надеяться;

– радоваться;

– ликовать.

Рис. 1.2.

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

Конечный автомат может быть реализован как программно, так и аппаратно. Программную реализацию можно выполнить на любом языке высокого уровня разными способами. На рис.1.3 представлена блок-схема программы, реализующей поведение автомата примера 1. Нетрудно увидеть, что топология блок-схемы программы повторяет топологию графа переходов автомата.

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

Рис. 1.3.

Аппаратную реализацию автомата рассмотрим во второй части этого раздела.

Пример 2. “Студент”

Автомат, модель которого представлена на рис.1.4, описывает поведение студента и преподавателей.

Рис. 1.4.

– состояния;

– входные сигналы: “н”, “2” и “5”.

– выходные реакции:

  • – отмечаем “н”;
  • – успокаивать;
  • – хвалим студента;
  • – поощряем;
  • – надеемся;
  • – предупреждаем;
  • – отчисляем;

Пример 31. Электронные часы (рис.1.5).

Электронные часы разнообразных функциональных возможностей являются одним из наиболее широко применяемых в быту электронных приборов, управление которыми построено на основе конечноавтоматной модели. Они обычно показывают: время, дату; у них имеется функции такие как “установка времени и даты”, “Секундомер”, “Будильник”и т.п. Упрощенная структурная схема электронных часов показана нарис.1.5

Рис. 1.5.

Регистры отображают либо время, либо дату, либо секундомер в зависимости от “Управления”. Устройство управления построено на основе модели конечного автомата.

Конечный автомат реагирует на нажатия кнопки “а” на корпусе переходом в состояние “Установка минут”, в котором событие нажатия кнопки “b” вызовет увеличение числа.

Устройство управления построено на основе модели конечного автомата, граф которого показан нарис.1.6

Рис. 1.6.

Итак. С одной стороны АВТОМАТ – устройство, выполняющее некоторые действия без участия человека. С другой стороны, АВТОМАТ – математическая модель, описывающая поведение технического устройства. В данном случае реальное устройство, система и т.д. рассматривается как некоторый “ЧЁРНЫЙ ЯЩИК” (рис.1.7).

Рис. 1.7.

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

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

То есть для описания автомата нужно использовать шестёрку вида , где

  • .

Автомат реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W.

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

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

Автомат называется детерминированным, если поведение автомата в каждый момент времени однозначно определено ( ,)

В зависимости от способа определения выходного сигнала в синхронных автоматах различают:

  1. Автомат первого рода ( Автомат Мили )
    • ;
  2. Автомат второго рода ( Автомат Мура )
    • ,

Источник: http://www.intuit.ru/studies/educational_groups/594/courses/242/lecture/6226?page=1

Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 2

2.4.2. Автомат Мили.: Автомат Мили отличается тем, что его функции выхода в момент t

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

Базис, Базис2, Минимизация. Далее в этой статье я оставил несколько разъясняющих пометок курсивом.

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

  • Комбинационные Схемы (КС) – не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.
  • Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.

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

Абстрактный автомат

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

В общем виде, не вдаваясь в подробности, абстрактный автомат можно представить следующим образом: Или, если перейти от иллюстрации к математическому описанию: A = Обозначения:

  1. Множество {A} – представляет собой множество значений на физических входах автомата.

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

  2. Множество {B} – представляет собой множество значений на физических выходах автомата.
  3. Множество {C} – а множество, которое представляет внутреннее состояние автомата – память.

    На будущее C0 будем обозначать начальное состояние автомата.

  4. δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние ai в которое переходит автомат из состояния aj.
  5. λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.

δ и λ не показаны на схеме для визуального упрощения. Такой автомат функционирует дискретно по времени, то есть значения входов, выходов и внутреннее состояние автомата изменяются в дискретные моменты времени. Итак мы в общем виде описали что есть Абстрактный автомат. Примером такого автомата может быть триггер, регистр ЭВМ или сумматор.

Выделяют 2 типа автоматов:

  1. Автоматы Мили. Описывается системой уравнений: c(t) = δ( a(t), c(t-1) ); b(t) = λ( a(t), c(t-1) ).
  2. Автоматы Мура. Описывается уравнениями: c(t) = δ( a(t), c(t-1) ); b(t) = λ( a(t), c(t) ).

Как видно состояние автомата c(t) в текущий момент времени является функцией его состояния в предыдущий момент времени и входного сигнала.

Отличаются автоматы видом функции выхода. В автомате Мили выходной сигнал определяется входным сигналом a(t) и состоянием автомата в предыдущий момент времени c(t-1). Выходной сигнал автомата Мура определяется парой входного сигнала a(t) и состояния в данный момент c(t).

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

Итак, на этом с матчастью окончено. Попробуем описать автоматы.

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

Способы задания автоматов

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

Однако, обычно функции δ и λ не заданы, и поведение автомата приходится описывать по-другому. Есть два основных способа задания автомата:

  1. При помощи графов.
  2. При помощи таблиц переходов и выходов.

Графы

Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое. Для графа Мили на дугах указываются сходные и выходные буквы. Выходные буквы пишутся над дугами, символизируя то, что выходное состояние зависит от состояния автомата в предыдущий момент времени.

Для графа автомата Мура на дугах записываются только входные буквы, выходные же указываются около вершин.

Важный момент: Если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат называется полным. Другими словами – если из каждой вершины определены переходы для каждой входной буквы.

В наших примерах автомат Мили является полным, а автомат Мура – частичным.

И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется недетерминированным. Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к детерминированному автомату, но это не всегда можно выполнить. Описание этого процесса я тоже упускаю, сразу нарисовав детерминированный автомат. На этом о графах всё.

Таблицы переходов и выходов

Графы нагляднее для человека, а таблицы — для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ).

В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы. Построим ТПВ для наших графов Мили и Мура.

Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.

Тпв графа мили

В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3.

Тпв графа мура

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

Пример синтеза автомата

При помощи абстрактных автоматов можно описать практически что угодно. Можно описать работу цифровой схемы, а можно – синтаксический или лексический анализатор. Попробуем описать триггер – чем не автомат? Чтобы задать граф нужно словесное описание алгоритма работы триггера.

Читаем: Кодируем входной и выходной алфавиты: A = {a0, a1}, где a0 – логическая 1 на входе R, a1 – логическая единица на входе S. B = {b0, b1}, где b0 – логический 0 на выходе Q, b1 – логическая единица на выходе Q. Строим граф автомата Мили: Вот такая забавная чебурашка получилась :-).

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

Затем её можно упростить: Нанесём полученную функцию на карту Вейча и минимизируем: Выпишем, что получилось: Строим по функции схему (Выполняли домашнее задание?): Немного непривычно видеть триггер в булевом базисе, поэтому переведём функцию в базис И-НЕ и нарисуем схему в нём:
А на схеме асинхронный RS триггер обозначается вот так:

Теперь если приложить немного старания, то можно самостоятельно синтезировать простую новогоднюю гирлянду.

  • Схемотехника
  • теория автоматов
  • абстрактный автомат
  • триггер

Источник: https://habr.com/post/91968/

2.2.4. Микропрограммный автомат с жесткой логикой. Автоматы Мили и Мура

2.4.2. Автомат Мили.: Автомат Мили отличается тем, что его функции выхода в момент t

Рассмотримосновные принципы построениямикропрограммных автоматов, являющихсяядром УУ процессора и АЛУ (пп.3.6.1, 3.6.2).

Типичнаяструктура микропрограммного автоматас жесткой логикой [1,3-5] управ­ленияпредставлена на рис. 2.17. Исходнойинформацией для УУ служит содержимоерегистра команды, флаги, тактовыеимпульсы и сигналы, поступающие с шиныуправле­ния.

Кодоперации, хранящийся в РК, используетсядля определения того, какие СУ и в какойпоследовательности должны формироваться,при этом, с целью уп­рощения логикиуправления, желательно иметь в УУотдельный логический сиг­нал длякаждого кода операции (I0,I1,…, Ik).Это может быть реализовано с по­мощьюдешифратора: кода операции, которыйпреобразует код j-йоперации, поступающей из регистракоманды (РК), в единичный сигнал на j-мвыходе.

Рис. 2.17. Микропрограммныйавтомат с жесткой логикой

Сигналыуправления, по которым выполняетсякаждая микрооперация, должны вырабатыватьсяв строго определенные моменты времени,поэтому все СУ «при­вязаны» к импульсамсинхронизации (СИ), формируемым узломсинхроимпуль­сов. Узелсинхроимпульсов после завершенияочередного такта работы добавляет ксодер­жимому счетчика тактов единицу.

К выходам счетчика подключен дешифратортактов, с которого и снимаются сигналытактовых периодов Т1,…,Тn.Во время i-готакта дешифратор тактов вырабатываетединичный сигнал на своем i-мвыходе.

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

Большоезначение здесь имеет состояние флагов,отражающих ход вычислений, и сигналы сшины управления. Эта информация такжепоступает на вход УУ, причем каждаялиния здесь рассматривается независимоот остальных.

Процесссинтеза схемы МПА с жесткой логикойназывается структурным син­тезом иразделяется на следующие этапы:

  • выбор типа логических и запоминающих элементов;
  • кодирование состояний автомата;
  • синтез комбинационной схемы, формирующей выходные сигналы.

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

РаботуУУ можно описать микропрограм­мой спомощью языка микроопераций или в видеграфа. По микропрограмме строитсясоответствующий операционный авто­маттипа Мура или Мили [3, 5-7].

АвтоматМура в общем случае строится следующимобразом. Пусть микропрограмма имеетвид, представленный на рис. 2.18,а. Блокожидает возникнове­ния u1=1и затемпроизводит выработку управляющихфунк­циональных сигналов 1­6в определенной последовательно­сти,зависящей от значений сиг­налов uu3.

Рис. 2.18. Примерпроектирования автомата Мура:

а – представлениев виде блок-схемы алгоритма;

б – то же в видеграфа

Каждоймикрокоманде, от­дельно представленнойна гра­фе, ставятся в соответствиеот­дельные состояния автомата, которыеотмечаются управляющими функциональны­мисигналами соответствующих микрокоманд.

Условияперехода от микро­команды к микрокомандепред­ставляются в виде конъюнкциивходных сигналов, влияющих на переход.Каждая конъюнкция выписывается так,чтобы набор значений входных переменных,обращающих конъюнкцию в 1, соответствовалусловию перехода. При безусловномпереходе конъюнкция заменяется наконстанту 1.

Началои конец микропрограммы отображаютсяначальным состоянием Q0автомата Мура, при этом предполагается,что автомат является циклическим, тоесть допускающим многократ­ноповторяющуюся выработку последовательностейуправляю­щих сигналов.

Графавтомата Мура, построенного по описаннымправилам для рассматриваемоймикропрограммы, представлен на рис.2.18,б.

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

Переходот микропрограммы к автомату Милииллюстриру­ет рис. 2.19. Начало и конецмикропрограммы представляются на­чальнымсостоянием автомата Q0.

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

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

Рис. 2.19. Примерпроектирования автомата Мили:

а– представление в виде блок-схемыалгоритма;

б – то же в видеграфа

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

Источник: https://studfile.net/preview/2970193/page:18/

Переход от автомата Мили к автомату Мура и обратно

2.4.2. Автомат Мили.: Автомат Мили отличается тем, что его функции выхода в момент t

Для задания автоматов существуют специальные формализованные языки.

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

К начальным языкам относятся: язык регулярных выражений, язык предикатных форм, язык логических схем алгоритма. Широкого применения эти языки не нашли. Для описания частного класса автомата оказался удобным начальный язык логических схем алгоритмов НЯЛСА.

Если рассматривать автомат с учетом его внутренних состояний, то необходимо определить функции перехода (из внутреннего состояния xi во внутреннее состояние xj не исключая i = j). Задание функций выходов означает, что каждой паре  поставлено в соответствие состояние выхода .

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

Каждая строка (столбец) таблицы переходов соответствует состоянию входов, а каждый столбец (строка) внутреннему состоянию.

X1X2X3X4
1X2X1X1X2
2X3X3X1X4
3X4X2X1X1

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

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

12
X1X1X2
X2X3
X3X4
X4X1

Функция выхода автомата также может быть задана в виде таблицы. При этом вид таблицы зависит от модели автомата (Мили, Мура).

Для автомата Мили столбцы соответствуют внутренним состояниям, строки – входным сигналам, в ячейках – выходные сигналы.

X1X2X3
1131
2231
3121

Запись 1 означает, что если подать на вход автомата, находящегося в состоянии Х1, сигнал 1, то на выходе будет 1.

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

121
Х1Х2Х3
1X1X2X3
2X1X2
3Х3

Табличный способ для асинхронного автомата

Как и для синхронного автомата, каждая ячейка таблицы переходов асинхронного автомата соответствует внутреннему состоянию, в которое перейдет автомат. Это состояние определяется внутренним состоянием в предыдущий момент времени и поданным на вход сигналом.

Устойчивое состояние асинхронного автомата, т.е. состояние, соответствующее устойчивому такту обозначается в таблице переходов круглыми скобками. Неустойчивое состояние – записывается без скобок.

123
X1X2X2Х3
X2X3(Х5)(Х2)
X3Х6(Х1)
X4Х1Х3
Х5(Х1)Х6Х4
Х6(Х4)Х6

Входной сигнал можно менять, когда автомат перешел в новое устойчивое состояние. Если устойчивого состояния нет, то происходит зацикливание (неустойчивое состояние).

Если автомат переходит из одного устойчивого внутреннего состояния под воздействием входного сигнала в другое состояние, то входной сигнал можно изменять только при «попадании» автомата в устойчивое состояние. Переход автомата из одного устойчивого состояния в другое устойчивое может осуществляться через несколько неустойчивых состояний.

Таблица выходов. 

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

12
X111
X22
X323
X41

Граф автомата – это связный граф, вершины которого соответствуют внутренним состояниям автомата, а дуги определяют переходы между состояниями.

Для автомата Мили:

Две вершины графа автомата xi и xj соединяются дугой, направленной от xi к xj, если в автомате имеется переход из состояния xi в состояние xj. Дуге графа приписывается входной сигнал и выходной сигнал . Если переход автомата из состояния xi в состояние xj происходит под воздействием нескольких входных сигналов, то дуге приписываются все эти сигналы через знак v (дизъюнкции).

Пример:

Для автомата Мура:

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

Для асинхронного автомата.

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

Матрица переходов представляет собой квадратную матрицу, строки и столбцы которой соответствуют внутренним состояниям автомата.

Элементы [i,j] указывают состояние входа автомата , при котором он переходит из внутреннего состояния xi в состояние xj, и состояние выхода, которое соответствует полному состоянию М.

В каждой строке матрицы перехода одно и тоже состояние входа не может встретиться более одного раза.

Если автомат из внутреннего состояния xi переходит в состояние xj под воздействием нескольких входных сигналов, то в соответствующей ячейке проставляется дизъюнкция состояния входа.

X1X2X3
X11221
X21v3/223
X321

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

Пусть на вход этого автомата поступает входное слово – (последовательность входных сигналов).

Назовем переменную  реакцией автомата, находящегося в состоянии а0, на входное слово .

Автомат Мили в ответ на входное слово длиной k выдает последовательность состояний длиной k+1 и выходное слово длиной k.

Зададим автомат Мура.

Найдем реакцию автомата Мура на входное слово – . Начальное состояние x1:

x1x4x2x1x4x3x5

Два автомата SА и SB с одинаковыми входным и выходным алфавитом называются – эквивалентными, если после установления их в начальное состояние реакции на любое входное слово совпадают.

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

Рассмотрим переход от автомата Мура к автомату Мили.

Пусть задан автомат Мура:

Необходимо построить автомат Мили, эквивалентный автомату Мура:

Функцию  определим следующим образом: если в автомате Мура имеются функции , то для автомата Мили можно записать следующую функцию выхода: .

Рассмотрим переход от автомата Мура к автомату Мили с помощью графа:

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

Переход от автомата Мура к Мили табличным способом:

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

Для автомата Мура

123
1X1X1X2X4
2X2X2X3X1
1X3X1X3X4
3X4X1X1X4

Для автомата Мили

123
X1123
X2211
X3113
X4113

Из самого способа построения автомата Мили очевидно, что он эквивалентен автомату Мура.

Для входной последовательности Ф поведение автоматов Sа и полностью совпадают. По индукции не трудно доказать, что любое входное слово конечной длины, поданное на входы автоматов Sа и SВ, установленных в начальное состояние x0 вызовет появление одинаковых выходных слов.

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

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

Задан автомат Мили Sа . Необходимо построить автомат Мура SВ.

Алфавиты должны совпадать:

Для определения множества XB каждому состоянию  поставим соответствующее множество пар вида , где  – это выходной сигнал приписанный дуге, входящей в xs.

Число элементов в множестве XS будет равно числу различных выходных сигналов на дугах автомата Мили SA, входящих в состояние xa Число внутренних состояний автомата Мура будет определяться объединением множеств всех XS.

XA => XB

Функция переходов  и функция выходов  определяется так: если в автомате Мили имеется переход из состояния xm в состояние xs под воздействием

и при этом выдается выходной сигнал

,

то в автомате Мура будет переход из множества состояний X’m, порождаемое внутренним состоянием xm под воздействием входного сигнала .

.

Функция выходов автомата Мура определяется следующим образом

В качестве начального состояния x0B можно взять любое состояние из множества, которое порождается начальным состоянием x0А.

Т.о. получается автомат SВ, эквивалентный автомату SA.

Автомат Мили Автомат Мура

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

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

Не нашли то, что искали? Воспользуйтесь поиском:

Источник: https://studopedia.ru/2_116084_perehod-ot-avtomata-mili-k-avtomatu-mura-i-obratno.html

Автоматы Мили и Мура. С-автомат. Законы функционирования. Основные различия

2.4.2. Автомат Мили.: Автомат Мили отличается тем, что его функции выхода в момент t

Билет №1

Определение ЦА. Основные понятия теории автоматов: ЦА конечные, синхронные, асинхронные, идеализированные, абстрактные, структурные. Абстрактная и структурная теория автоматов.

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

ЦА конечны, когда множество входных и выходных сигналов, а также число входных и выходных каналов и множество состояний автомата конечны.

Синхронный ЦА – входные сигналы действуют в строго определенные моменты времени при Т=конст, определяемые генератором синхронизирующих импульсов, в которые возможен переход автомата из одного состояния в другое.

Асинхронный ЦА – Т конст и определяется моментами поступления входных сигналов, а переход автомата из одного состояния в другое осуществляется при неизменном состоянии входа.

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

Абстрактный ЦА  – шестикомпонентный вектор S = {A,z,w,σ,λ,a1}, у которого: А- множество состояний автомата, Z – входные сигналы, W- выходные сигналы, σ- функция переходов, λ- функция выходов, а1 – начальное состояние автомата.

Структурный ЦА – учитывает структуру входных и выходных сигналов, а также его внутреннее устройство на уровне структурных схем.

Структурная теория ЦА изучает общие приемы построения структурных схем автоматов на основе элементарных автоматов.

Абстрактная теория ЦА – изучаются наиболее общие законы их поведения без учета конечной структуры автомата и физической природы информации.

Билет №2

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

Автомат Мили – a(t+1) = σ (a(t), z(t)); w(t) = λ (a(t), z(t)); a(0) = a1, t= 0,1,2,…

Автомат Мура – a(t+1) = σ (a(t), z(t)); w(t) = λ (a(t)); a(0) = a1, t= 0,1,2,…

С-автомат: под абстрактным С-автоматом понимают математическую модель цифрового устройства, определяемую восьмикомпонентным вектором S = {A,Z,W,U,σ,λ1, λ2,a1}, где А- множество состояний, Z- входной алфавит, W- выходной алфавит автомата Мили, U- выходной алфавит автомата Мура, σ- функция переходов автомата, λ1- функция выходов автомата Мили, λ2- функция выходов автомата Мура, а1 – начальное состояние.

Автомат без памяти(КС): Алфавит состояний такого автомата содержит единственную букву, поэтому понятие функции переходов вырождается и становится ненужным для описания работы автомата, т.е. выходной сигнал в данном такте зависит только от входного сигнала того же такта и никак не зависит от ранее принятых сигналов.

Автономный автомат: В таком автомате входной алфавит состоит из одной буквы. Автомат задается четырьмя объектами: А, W, σ, λ с возможным выделением начального состояния а1.

Если автомат конечен и число его состояний равно к, то среди значений а(1), А(2),…, а(к) найдутся повторяющиеся состояния.

АА используются для построения генераторов периодических последовательностей, генераторов синхросерий и в других задающих устройствах.

Автомат без выхода: В таком автомате выходной алфавит содержит только одну букву. Автомат задается тремя объектами: А, Z, σ. Из функций, задающих поведение автомата, сохраняется лишь функция переходов.

Управляющие и операционные автоматы: ОА реализует действия над исходной информацией (словами), т.е. является исполнительной частью операционного устройства, а УА управляет работой ОА, т.е.

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

УА используются не только в операционных устройствах вычислительной техники в системе УА-ОА, но и в разнообразных системах автоматики по управлению технологическими процессами и объектами.

Микропрограммные автоматы: Алгоритм записываемый с помощью микроопераций и логических условий, называется микропрограммой.

Билет №3

Автоматы Мили и Мура. С-автомат. Законы функционирования. Основные различия.

Автомат Мили – a(t+1) = σ (a(t), z(t)); w(t) = λ (a(t), z(t)); a(0) = a1, t= 0,1,2,…

Автомат Мура – a(t+1) = σ (a(t), z(t)); w(t) = λ (a(t)); a(0) = a1, t= 0,1,2,…

Эти автоматы различаются способом определения выходного сигнала.

В автомате Мили функция λ определяет выходной сигнал в зависимости от состояния автомата и входного сигнала в момент времени t, а в автомате Мура накладываются ограничения на функцию λ, заключающиеся в том, что выходной сигнал зависит только от состояния автомата и не зависит от значения входных сигналов. Выходные сигналы ЦА Мура отстают на один такт от выходных сигналов ЦА Мили, эквивалентного ему.

С-автомат: под абстрактным С-автоматом понимают математическую модель цифрового устройства, определяемую восьмикомпонентным вектором S = {A,Z,W,U,σ,λ1, λ2,a1}, где А- множество состояний, Z- входной алфавит, W- выходной алфавит автомата Мили, U- выходной алфавит автомата Мура, σ- функция переходов автомата, λ1- функция выходов автомата Мили, λ2- функция выходов автомата Мура, а1 – начальное состояние.

a(t+1) = σ (a(t), z(t)); w(t) = λ 1(a(t), z(t)); u(t) = λ (a(t)); a(0) = a1, t= 0,1,2,…

Отличие С-автомата в том, что он одновременно реализует две функции выходов λ1 и λ2, каждая из которых характерна для модели Мили и модели Мура в отдельности.

От С-автомата легко перейти к автоматам Мили и Мура с учетом возможных сдвигов выходных сигналов на такт, аналогично тому, как возможен переход от автомата Мили к автомату Мура и наоборот.

Много реальных автоматов работает по модели С-автомата.

Билет №4

Источник: https://megaobuchalka.ru/13/40664.html

Дискретная математика (стр. 11 )

2.4.2. Автомат Мили.: Автомат Мили отличается тем, что его функции выхода в момент t

Определение. Абстрактным конечным автоматом называется шестерка объектов

,

где – конечное непустое множество состояний;

– начальное состояние;

– конечное непустое множество входных сигналов;

– множество выходных сигналов;

– функция переходов;

– функция выходов.

По характеру отсчета дискретного времени конечные автоматы делятся на синхронные и асинхронные.

В синхронных конечных автоматах моменты времени (такты), в которые автомат считывает входные сигналы, определяются принудительно синхронизирующими сигналами.

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

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

4.1.2. Автоматы Мили и Мура

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

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

Она является двухаргументной и символ в выходном канале обнаруживается только при наличии символа во входном канале . Функции перехода и выхода для автомата Мили можно записать в виде

где – длительность такта.

Зависимость выходного сигнала только от состояния представлена в автоматах типа Мура. В автоматах этого типа функция выходов определяет значение выходного символа только по одному аргументу – состоянию автомата. При этом символ в выходном канале существует все время, пока автомат находится в состоянии . Для автомата Мура функции перехода и выхода можно записать как

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

4.1.3. Способы задания конечных автоматов

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

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

Для сложных автоматов графическое представление становится слишком громоздким. Более целесообразным в этом случае представляются различные табличные способы задания в форме таблиц переходов и выходов либо в форме матриц смежности направленного графа.

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

Рис. 4.1. Автомат, описывающий поведение отца,
отправившего сына в школу

Автомат имеет четыре состояния и два входных сигнала – оценки, получаемые сыном в школе: {2,5}.

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

Выходы автомата будем интерпретировать как действия отца следующим образом: – брать ремень; – ругать сына; – успокаивать сына; – надеяться; – радоваться; – ликовать.

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

Каждая предыстория определяет текущее состояние автомата (отца), при этом некоторые предыстории эквивалентны (те, что приводят автомат в одно и то же состояние). История 2,2,5 эквивалентна пустой истории. Текущее состояние автомата представляет все то, что автомат знает о прошлом с точки зрения его будущего поведения.

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

Кроме того, рассмотренный автомат является, очевидно, автоматом Мили, т. к. реакция зависит как от состояния отца, так и от полученной оценки.

Эквивалентом структурного представления автомата может являться, например, матрица смежности орграфа. В отличие от обычной матрицы смежности (см. разд. 3.1.

2) в качестве элемента записываются входной и выходной сигналы, соответствующие переходу автомата из -го состояния в -е.

Если переход происходит под воздействием нескольких сигналов, элемент представляет собой множество пар «вход/выход» для этого перехода, соединенных знаком дизъюнкции.

Для рассмотренного примера матрица смежности задана табл. 4.1.

Таблица 4.1

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

Для автомата Мили таблица переходов в общем виде приведена ниже.

Таблица 4.2

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

Табличное описание автомата Мура можно записать как табл. 4.3.

Таблица 4.3

Для рассмотренного примера, который представляет собой автомат Мили, таблицы переходов и выходов имеют вид табл. 4.4 и табл. 4.5.

Таблица 4.4

(5)

(2)

Таблица 4.5

(5)

(2)

4.1.4. Реализация конечных автоматов

Рассмотрим два вида реализации конечного автомата: программную и аппаратную.

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

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

), можно воспитание сына поручить компьютеру.

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

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

Таким образом, общий подход к аппаратной реализации конечного автомата совпадает с общей процедурой синтеза логических схем, описанной в разд. 2.3, и включает следующие шаги:

· входные и выходные сигналы и внутренние состояния автомата кодируются двоичными кодами;

· по таблицам переходов и выходов составляются кодированные таблицы переходов и выходов – фактически табличное задание отображений и ;

· по кодированным таблицам переходов и выходов формируются аналитические выражения логических функций и проводится их минимизация;

· полученные минимальные формы реализуются в заданном элементном базисе;

· решаются схемотехнические вопросы синхронизации – привязки моментов выдачи выходного сигнала и изменения состояния внутренней памяти к моментам поступления входных сигналов на вход автомата.

Рассмотрим реализацию автомата из рассмотренного примера. Входных сигналов два; мы их закодируем так: , . Выходных сигналов шесть. Закодируем их: , , …, . Внутренних состояний четыре. Закодируем их: , , , .

Таким образом, имеем: , , . Структурная схема этого автомата после двоичного кодирования имеет вид, показанный на рис. 4.

2, где – функциональный преобразователь без памяти, реализующий отображения и , БП – блок памяти.

Рис. 4.2. Структурная схема автомата

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

Таблица 4.6

0

0

0

0

1

0

1

0

0

0

1

1

0

0

0

1

0

1

0

1

0

0

0

0

0

1

1

0

1

0

1

0

1

0

0

1

1

1

0

0

1

0

1

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

1

1

1

0

1

После записи логической формулы и минимизации в классе ДНФ, как это рассмотрено в разд. 2.4, получим аналитические выражения для всех двоичных функций, реализация которых показана на рис. 4.3.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13

Источник: https://pandia.ru/text/78/205/16088-11.php

Medic-studio
Добавить комментарий