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


 

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

45790. Ценовая политика фирмы. Методы ценообразования. Ценовые стратегии 23.26 KB
  При этом фирма должна учитывать множество факторов при выборе оптимального метода и стратегии ценообразования: издержки производства объемы и характер спроса тип рынка цены конкурентов и др. Именно в этой ситуации актуально звучит маркетинговое определение цены как суммы денег которую готов уплатить потенциальный потребитель. существует определенный алгоритм методика установления исходной цены на товары. При определении цены прежде всего фирме предстоит решить каких именно целей она стремится достичь с помощью конкретного товара.
45791. Сегментация рынка, отбор целевых критериев рынка. Критерии сегментации 17.76 KB
  Сегментирование рынка – представляет собой разбивку рынка на четкие группы покупателей для каждой из которых могут потребоваться отдельные товары и или комплексы маркетинга. Какогото единого метода сегментирования рынка не существует: используются варианты включающие от отсутствия сегментирования до полного сегментирования. Для того чтобы целевой рынок с помощью маркетингового исследования сделать более доступным для продавца остается выяснить: нет ли внутри существующего рынка как целого сегментов со специфическими требованиями к...
45792. Товарная политика фирмы: цели и основные составляющие 51.33 KB
  Котлеру: Три уровня товара: Классификация товаров широкого потребления: товары повседневного спроса – товары которые потребитель обычно покупает часто без раздумий и с минимальными усилиями на их сравнение м у собой товары импульсивной покупки товары для экстренных случаев сигареты мыло газеты; товары предварительного выбора – товары которые потребитель в процессе выбора покупки как правило сравнивает м у собой по показателям пригодности цены качества и внешнего оформления мебель одежда подержанные автомобили и основные...
45795. МЕТОД ИЗМЕРЕНИЯ ДИФФЕРЕНЦИАЛЬНОГО СОПРОТИВЛЕНИЯ НА ПЕРЕМЕННОМ ТОКЕ 399 KB
  змерение напряжения стабилизации проводят следующим образом. Через, испытываемый прибор, подключенный к клеммам Х1 и Х2, пропускают заданный ток стабилизации и измеряют разность напряжений между напряжением...
45796. ВЗАИМОДЕЙСТВИЕ СПРОСА И ПРЕДЛОЖЕНИЯ 28.36 KB
  Через эти колебания устанавливается тот уровень цен при котором обеспечивается равновесие спроса и предложения и в конечном итоге равновесие производства и потребления. Рассмотрим сначала эластичность спроса. Эластичность спроса по цене прямая эластичность спроса это степень чувствительности спроса на какойнибудь товар к изменению цены на этот товар.
45797. Значение конкуренции в современной экономике 15.71 KB
  Основными методами конкуренции являются: повышение качества продукции снижение цен война цен реклама развитие до и послепродажного обслуживания создание новых товаров и услуг с использованием достижений НТР и т. конкуренции: активизация инновационного процесса гибкое приспособление к спросу высокое качество продукции высокая производительность труда минимум издержек реализация принципом оплаты по количеству и качеству труда возможность регулировки со стороны государства. конкуренции: победа одних и поражение...
45798. Модель безубыточности производства. Точка безубыточности 31.18 KB
  Отсюда находим критический объем: Q' = F pv где Q' – точка безубыточности критический объем в натуральном выражении; v – переменные затраты на единицу продукции. Критический объем производства и реализации продукции можно рассчитать не только в натуральном но и в стоимостном выражении: S = F p p v = Q' p где S – критический объем производства и реализации продукции. Приведенные выше формулы расчета критического объема производства и реализации в натуральном и стоимостном выражении справедливы лишь когда выпускается только один...