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


 

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

50074. Визначення роботи виходу електронів з металу за допомогою явища термоелектронної емісії 74 KB
  Мета роботи: дослідження явища термоелектронної емісії та визначення роботи виходу електронів з вольфраму. Розв’язавши цю систему рівнянь визначимо роботу виходу А = 4. визначити роботу виходу електрона з металу вольфраму.
50075. ОПРЕДЕЛЕНИЕ КОНЦЕНТРАЦИИ САХАРНОГО РАСТВОРА САХАРИМЕТРОМ 126.5 KB
  К оптически активным веществам относятся некоторые кристаллы и растворы например кварц и раствор сахара в дистиллированной воде. Целью лабораторной работы является определение величины удельного вращения ρ для раствора сахара для чего используется эталонный раствор а также определение концентрации сахара в некотором исследуемом растворе. Описание установки Концентрация раствора сахара определяется прибором который называется сахариметром. Его основными частями являются поляризатор и анализатор между которыми помещается трубка с...
50076. ИЗУЧЕНИЕ УСТРОЙСТВА И РАСЧЕТ ПЕРВИЧНЫХ СРЕДСТВ ПОЖАРОТУШЕНИЯ 376 KB
  В качестве первичных средств пожаротушения применяют воду песок асбестовое или войлочное полотно огнетушители. Огнетушители надежное средство при тушении загораний до прибытия пожарных подразделений. Воздушно-пенные огнетушители В качестве веществ для получения воздушно-механической пены широко используют различные пенообразователи поверхностно-активные вещества и смачиватели.
50077. ДИСПЕРСИЯ ПРИЗМЫ 304 KB
  Дисперсией света называются явления обусловленные зависимостью показателя преломления от частоты или длины волны излучения: 1 Один из важнейших выводов электромагнитной теории света Максвелла состоит в том что показатель преломления электромагнитных волн равен в системе СГСэ: 2 Здесь ε и μ диэлектрическая и магнитная проницаемости среды постоянные которые в первоначальной теории полагались не зависящими от частоты падающего света. Для того чтобы получить соотношение связывающее показатель преломления с длиной волны необходимо...
50078. Техніка ведення мяча 22.5 KB
  Техніка ведення м’яча. Ведення м’яча здійснюється за допомогою переміщень у процесі яких застосовується біг іноді ходьба. Ведення зовнішньою частиною підйому виконується несильними ударами в нижню частину м’яча з метою надати йому зворотного руху щоб він сильно не віддалявся від гравця. При веденні внутрішньою частиною підйому футболіст спрямовує м’яч перед собою носок ноги перед доторком до м’яча трохи відводиться назовні.
50080. Циклические программы 47.5 KB
  Операторов цикла в Паскале три: for repet while. Оператор For Оператор состоит из заголовка в котором определяется порядок изменения переменной параметра цикла и тела цикла являющегося многократно повторяющимся алгоритмом. Общий вид оператора: For – параметр цикла : = начальное значение to конечное значение do оператор; {тело цикла}. Этот оператор применяется если начальное значение конечного значения; For – параметр цикла:= начальное значение downto конечное значение do оператор; применяется если начальное значение конечного значения.
50081. ПРОЧНОСТНЫЕ ХАРАКТЕРИСТИКИ МАТЕРИАЛОВ В РАСЧЕТАХ ПО МЕТОДУ ПРЕДЕЛЬНЫХ СОСТОЯНИЙ 51.5 KB
  Соответствующими стандартами установлены также другие нормативные характеристики материалов объемная масса модули упругости и сдвига коэффициенты трения сцепления характеристики ползучести усадки температурного расширения усушки набухания и другие. Возможные отклонения нормативных характеристик конструкционных материалов и грунтов в неблагоприятную сторону учитываются коэффициентами надежности по материалу и грунту . Эти коэффициенты учитывают ряд факторов не проявляющихся при стандартных испытаниях но встречающихся в практике...
50082. Визначення показника заломлення скляної плоскопаралельної пластинки інтерференційним методом 674 KB
  На оптичній лаві послідовно розташовані джерело світла лазер 1 типу ЛГ56 екран 2 в центрі якого розміщено мікрооб’єктив та плоскопаралельна скляна пластинка 3 товщиною d. Відбиваючись від її передньої та задньої граней промені світла накладаються і утворюють на екрані інтерференційну картину у вигляді концентричних кілець  так звані смуги однакового нахилу. В чому полягає суть методу визначення показника заломлення скляної пластинки в даній роботі Що називається явищем інтерференції світла Які хвилі називаються когерентними...