22117

Частичные автоматы

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Оказывается что для любого автомата Мили существует эквивалентный ему автомат Мура и обратно для любого автомата Мура существует эквивалентный ему автомат Мили. Рассмотрим алгоритм перехода от произвольного конечного автомата Мили к эквивалентному ему автомату Мура. Требуется построить эквивалентный ему автомат Мура Sb = {Ab Xb Yb b b} у которого Xb = Xa Yb = Ya т. Для определения множества состояний Ab автомата Мура образуем всевозможные пары вида ai yg где yg – выходной сигнал приписанный входящей в ai дуге.

Русский

2013-08-04

194 KB

2 чел.

Лекция 3

Частичные автоматы

В инженерной практике часто встречаются автоматы, на входы которых некоторые последовательности сигналов никогда не подаются. Такие последовательности будем называть запрещенными входными словами данного автомата, а сам автомат – частичным автоматом. У частичного автомата функции переходов и выходов определены не на всех парах ai, xj. На месте неопределенных состояний и выходных сигналов ставится прочерк. При синтезе обычно производят доопределение частичного автомата, чтобы его схемная реализация получилась как можно проще.

xj\ai

a0

a1

a2

a3

x1

a1/y1

a3/y3

a2/y2

a2/y1

x2

- / -

- / -

a0/y4

a0/y2

Эквивалентность автоматов

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

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

Рассмотрим алгоритм перехода от произвольного конечного автомата Мили к эквивалентному ему автомату Мура.

Пусть дан конечный автомат Мили Sa = {Aa, Xa, Ya, a, а},имеющий множество состояний Aa = {a0,a1, …, ai, …, an}, множество входных и выходных сигналов Xa = {x1, x2, …,xj, …, xm} и Y = {y1, y2, …, yg, …, yk}, а также функции переходов a(a,x) и выходов a(a,x).

Требуется построить эквивалентный ему автомат Мура Sb = {Ab, Xb, Yb, b, b}, у которого Xb = Xa, Yb = Ya, т.к. множества входных и выходных сигналов у эквивалентных автоматов должны совпадать.

Для определения множества состояний Ab автомата Мура образуем всевозможные пары вида (ai, yg), где yg – выходной сигнал, приписанный входящей в ai дуге.  Например, для вершины ai  имеем пары (ai, y1), (ai, y2), (ai, y3). Если такие пары мы образуем для всех вершин, то получим множество пар, которое является множеством состояний автомата Мура Ab =  {(a0, y1), (a0, y2), …, (an, yk)} = {b1, b2, …, bn}, где bl = (ai, yg).

  y1

  y2 ai

  y3

   y1

Функции выходов b и переходов b определим следующим образом. Каждому состоянию автомата Мура, представляющему собой пару вида (ai, yg) поставим в соответствие выходной сигнал yg, т.е. функция выходов равна yg = b[(ai, yg)] = b[bl]. Если в автомате Мили Sa был переход a(ai, xj) = as и при этом выдавался выходной сигнал a(ai, xj) = yp, то в эквивалентном автомате Мура будет переход из множества состояний (ai, yg), где g G, G – множество номеров выходных сигналов, приписанных к входящей ai дуге, в состояние (as, yp) под действием входного сигнала xj. Проиллюстрируем это на рисунке.

Автомат Мили (фрагмент).    Автомат Мура эквив. авт. Мили.

Автомат Мили имеет два состояния, а автомат Мура три : (ai, yf), (ai, yr), (ai, yp).  Если автомат Мили был в состоянии ai и пришел входной сигнал xj, то должен выработаться выходной сигнал yp. Поэтому в автомате Мура из состояний, порождаемых ai, т.е. из состояний (ai, yf) и (ai, yr) при поступлении xj переход должен идти в состояние, отмеченное выходным сигналом yp, т.е. в (as, yp). В качестве начального состояния автомата Мура можно взять любое состояние из множества (a0, yr).

 Рассмотрим пример.

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

В автомате Мили Xa = {x1, x2}, Ya = {y1,y2}, Aa = {a0, a1,a2}.

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

Xb = Xa = {x1, x2}, Yb = Ya = {y1, y2}.

Построим множество состояний Ab автомата Мура, для чего найдем множества пар, порождаемых каждым состоянием автомата Sa.

Для состояния a0:  {(a0, y1), (a0, y2)} = {b1, b2}

Для состояния a1:  {(a1, y1)} = {b3}

Для состояния a2:  {(a2, y1), (a2, y2)} = {b4, b5}

Отсюда имеем множества As состояний автомата Мура

As = {b1, b2, b3, b4, b5}. Для нахождения функции выходов b с каждым состоянием, представляющим собой пару вида (ai, yg), отождествим выходной сигнал, являющийся вторым элементом этой пары. В результате имеем:

 b(b1) = b(b3) = b(b4) = y1; b(b2) = b(b5) = y2.

 Построим функцию переходов b, т.к. в автомате Sa из состояния  a0 есть переход под действием сигнала x1 в состояние a2 с выдачей y1,то из множества состояний {b1, b2}, порождаемых a0, в автомате Sb должен быть переход в состояние (a2, y1) = b4 под действием сигнала x1. Аналогично,  из {b1, b2} под действием x2 должен быть переход в (a0, y1) = b1. Из (a1, y1) = b3 под действием x1 переход в (a0, y1) = b1, а под действием x2 – в (a2, y2) = b5. Наконец из состояний {(a2, y1), (a2, y2)} = {b4, b5} под действием x1 в (a0, y2) = b2, а под действием x2 – в (a1, y1) = b3. В результате имеем эквивалентный автомат Мура с таблицей переходов:

yg

y1

y2

y1

y1

y2

xj\bi

b1

b2

b3

b4

b5

x1

b4

b4

b1

b2

b2

x2

b1

b1

b5

b3

b3

В качестве начального состояния автомата Sb можно взять любое из состояний b1 или b2, т.к. оба порождены состоянием a0 автомата Sa.

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

Sb ={Ab, Xb, Yb, b, b}.

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

Sa = {Aa, Xa, Ya, a, a}. По определению эквивалентности имеем

Xa = Xb; Ya = Yb. Кроме того, Aa = Ab, a= b. Остается только построить функцию выходов. Если в автомате Мура b(ai, j) = as, а b(as) = yg, то в автомате Мили a(ai, xj) = yg.

Другими словами a(ai, xj) = b(b(ai, xj)). Таким образом таблица переходов автоматов Мили и Мура совпадают. А таблица выходов эквивалентного автомата Мили строится так, что в каждую клетку таблицы записывается выходной сигнал, которым отмечено состояние, расположенное в данной клетке.

Например. Пусть дан  автомат Мура:

xj\yi

y1

Y1

y3

y2

y3

a0

A1

a2

a3

a4

x1

a1

A4

a4

a2

a2

x2

a3

A1

a1

a0

a0

Тогда эквивалентный ему автомат Мили имеет следующую совмещенную таблицу переходов и выходов.

a0

a1

a2

a3

a4

x1

a1/y1

a4/ y3

a4/ y3

a2/ y3

a2/ y3

x2

a3/ y2

a1/ y1

a1/ y1

a0/ y1

a0/ y1


 

А также другие работы, которые могут Вас заинтересовать

28818. Как происходило становление советской политической и социально-экономической системы? Деятельность большевистской партии и советского правительства в 1917-1920гг. 20.72 KB
  Власть и командные высоты в экономике крупная и средняя промышленность внешняя торговля финансовая системы транспорт оставались в руках большевиков которые не отказывались от конечной цели социализма шли к ней не прямым политики военного коммунизма а обходным путем с помощью товарноденежных отношений. Реальная политическая власть принадлежала Президиуму ВЦИК и Совету народных комиссаров СНК который присвоил себе не только исполнительную но и законодательную власть. Особое внимание уделялось формированию аппарата...
28819. Объясните название и сущность политики военного коммунизма 14.24 KB
  Решение о прекращении военного коммунизма было принято 21 марта 1921 года на X съезде РКПб и введен НЭП. Политика военного коммунизма включала комплекс мероприятий затронувших экономическую и социальнополитическую сферу. Основой военного коммунизма были чрезвычайные меры в снабжении городов и армии продовольствием свертывание товарноденежных отношений национализации всей промышленности включая мелкую продразверстка снабжение населения продовольственными и промышленными товарами по карточкам всеобщая трудовая повинность и...
28820. Каковы причины, особенности и последствия гражданской войны в России 15.36 KB
  В ходе Гражданской войны от голода болезней террора и в боях погибло по различным данным от 8 до 13 млн человек в том числе около 1 млн бойцов Красной Армии. Эмигрировало из страны до 2 млн человек. По одним данным в 1921 году в России насчитывалось 45 млн беспризорников по другим в 1922 году было 7 млн беспризорников.
28821. На каких принципах был построен СССР в 1922г? Какие альтернативные варианты объединения обсуждались 14.64 KB
  I съезд Советов СССР утвердил Декларацию и Договор об образовании Союза Советских Социалистических республик. II съезд Советов СССР принял первую Конституцию СССР она состояла из Декларации и Договора об образовании СССР. Конституция признавала республики суверенными государствами с правом свободного выхода из Союза внесения в свои конституции изменений в соответствии с Конституцией СССР.
28822. Какое значение имел НЭП для социалистического строительства? Почему он был свернут 20.45 KB
  Достижения нэпа значительны: к 1925 г. Вместе с тем успехи нэпа не следует преувеличивать. Противоречия нэпа проявлялись в: экономике техническая отсталость промышленности высокие темпы ее восстановления острая потребность в обновлении производственных мощностей нехватка капиталов внутри страны. невозможность широкого привлечения иностранных капиталовложений абсолютное преобладание мелких полунатуральных крестьянских хозяйств на селе; социальной сфере усиление неравенства неприятие нэпа значительной частью рабочего класса и...
28823. Планы осуществления индустриализации в СССР: проекты, цели, пути осуществления, итоги 16.39 KB
  Задачу осуществления индустриализации т. Где взять капиталы для финансирования промышленности Какие темпы индустриализации дадут стабильный устойчивый рост Какую пену готово заплатить за неизбежные лишения общество К 1927 г. первый подход обоснованный видными ученымиэкономистами: капиталы для финансирования индустриализации дадут развитие частного предпринимательства привлечение иностранных займов расширение торгового оборота; темпы индустриализации должны быть высокими но при этом ориентироваться на реальные возможности а не на...
28824. «Великий перелом» в сельском хозяйстве и его цена 19.12 KB
  когда крестьяне продавали зерно по выгодным для себя рыночным ценам а государство сделало успешные закупки. Деревня была обеспокоена внешними проблемами и крестьяне не желали продавать зерно. Серьезные ошибки были допущены в политике цен которая стимулировала развиьтие технических культур и животноводства за счет посевов зерновых. Страх перед войной побуждал крестьянина насколько это было возможно придерживать зерно.
28825. Почему «культурная революция» является составной частью «Большого скачка»? Каковы ее задачи 16.46 KB
  Иными словами сущность культурной революции это в первую очередь коренное качественное изменение субъекта культурноисторического процесса выражающееся в приобщении масс и каждого отдельного человека к сознательному историческому творчеству. Сущность культурной революции можно сформулировать и как социалистическое обновление условий и характера творческой деятельности в области культуры и системы распределения и потребления духовных ценностей и связанный с этим резкий культурный подъем общества. Основу ленинской концепции культурной...
28826. Эволюция советской политической системы в 20-30гг. Было ли неизбежно становление тоталитарного режима в СССР 15.43 KB
  Она поддерживалась всей мощью государства на всех уровнях.Тоталитаризм Одна из форм устройства авторитарного государства характеризующаяся его полным господством над всеми сторонами жизни; тоталитарный режим. Так происходит провоцирование ГОСУДАРСТВА на расширение его контрольных функций то есть подталкивание к ТОТАЛИТАРИЗМУ. В итоге общество получает полное огорчение по поводу деятельности ГОСУДАРСТВА и начинает ратовать за освобождение от тоталитаризма.