Конспект лекций Киров 2010 удк 681. 332




НазваниеКонспект лекций Киров 2010 удк 681. 332
страница7/17
Дата публикации21.08.2013
Размер0.75 Mb.
ТипКонспект
zadocs.ru > Химия > Конспект
1   2   3   4   5   6   7   8   9   10   ...   17
^

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


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

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



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

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

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

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



x1x4x2x1x4x3x5



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

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

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

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



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







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

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

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


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

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







1

2

3

1

X1

X1

X2

X4

2

X2

X2

X3

X1

1

X3

X1

X3

X4

3

X4

X1

X1

X4


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





1

2

3

X1

1

2

3

X2

2

1

1

X3

1

1

3

X4

1

1

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

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

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

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

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





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







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



XA => XB

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



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

,

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

.

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



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

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




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

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

1   2   3   4   5   6   7   8   9   10   ...   17

Похожие:

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине "инвестирование"
Конспект лекций по дисциплине «Инвестирование» для студентов экономических специальностей всех форм обучения Сост.: В. М. Гридасов...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине “Каналообразующие устройства”, 2010 Перечень лекций
Тема №1 (4 часа) Назначение, основные параметры и состав каналообразующих устройств 5

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций Витебск 2010 министерство образования республики...
Конспект предназначен для самостоятельного изучения, подготовки к практическим занятиям и экзамену по экономической теории

Конспект лекций Киров 2010 удк 681. 332 iconЭтика курс лекций (на основе книги: Этика (конспект лекций)
Этика (конспект лекций). – М.: «Приор-издат», 2002. Автор-составитель Аристотель. Никомахова этика. Сочинения: в 4-х т. Т. М.: Мысль,...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций для студентов направления 070104 «Морской и речной транспорт»
Конспект лекций рассмотрены и одобрены на заседании кафедры «Судовождение» кгмту

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по патологической анатомии инфекционных болезней. Киров, 2003
Вирусные инфекции представляют собой одну из многочисленных групп инфекционных заболеваний разнообразных по клиническому течению...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций Утверждено Редакционно-издательским советом в качестве...
Чижов М. И., Юров А. Н. Информатика и информационные системы: Конспект лекций. Воронеж: Воронеж гос техн ун-т, 2003. 148 с

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине «Безопасность жизнедеятельности»
Безопасность в чрезвычайных ситуациях и гражданская оборона. Конспект лекций. Рубцов Б. Н. М. Миит, 2001

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций
Цифровые системы управления и обработки информации. Конспект лекций. Модуль 1: Организация и программирование систем чпу. (для студентов...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций для студентов сектора второго высшего образования...
Конспект лекций разработан кандидатом экономических наук, доцентом кафедры «Экономическая теория и кибернетика» Одесского государственного...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов