22116

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

Лекция

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

Существует несколько способов задания работы автомата но наиболее часто используются табличный и графический. Совмещенная таблица переходов и выходов автомата Мили: xj ai a0 an x1 a0x1 a0x1 anx1 anx1 xm a0xm a0xm anxm anxm Задание таблиц переходов и выходов полностью описывает работу конечного автомата поскольку задаются не только сами функции переходов и выходов но и также все три алфавита: входной выходной и алфавит состояний. Для задания автомата Мура требуется одна таблица поскольку в этом...

Русский

2013-08-04

362 KB

25 чел.

Лекция 2

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

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, , } , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов и выходов . При этом среди множества A = {a0,a1,…, an} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

  1.  Табличный способ. При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

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

xj\aj

a0

an

x1

(a0,x1)

( an,x1)

xm

( a0,xm)

( an,xm)

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

xj\aj

a0

an

x1

(a0,x1)

( an,x1)

xm

( a0,xm)

( an,xm)


Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = [ ai,xj], в которое автомат перейдет из состояния ai под воздействием сигнала xj; а в таблице выходов – соответствующий этому переходу выходной сигнал yg = [ ai,xj].

Совмещенная таблица переходов и выходов автомата Мили:

xj\ai

a0

an

x1

(a0,x1)/ (a0,x1)

(an,x1)/ (an,x1)

xm

(a0,xm)/ (a0,xm)

(an,xm)/ (an,xm)

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

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

Отмеченная таблица переходов автомата Мура:

yg

(a0)

(an)

xj\ac

a0

an

x1

(a0,x1)

(an,x1)

xm

(a0,xm)

(an,xm)

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

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

Приведем примеры табличного задания автоматов Мили и Мура:

По этим таблицам можно найти реакцию автомата на любое входное слово. Например.

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

x1x2x2x2x1…    x1x2x2x2x1

a0a1a0a0a0a1     a0a2a4a1a4

y1y1y2y2y1     y2y1y2y1y2

  1.  Графический способ задания автомата (задание автомата с помощью графа).

Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as, если в автомате имеется переход из ai в as, т.е. as =  (ai, xj). В автомате Мили дуга отмечается входным сигналом xj, вызвавшим переход, и выходным сигналом yg, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

а)      б)


 

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

13734. История отечества. Тест. Вариант 1 97.5 KB
  Вариант №1 Часть 1 А1. В каком веке была создана Русская Правда свод законов Древнерусского государства 1 IX в. 2 X в. 3XI в. 4XII в. А2. Кто из названных лиц благословил войско Дмитрия Донского
13735. История отечества. Тест. Вариант 2 124 KB
  Вариант №2 Часть 1 А1. Какое из названных событий произошло в XI в. 1 принятие христианства на Руси 2 создание Русской Правды 3 первое летописное упоминание Москвы 4 создание Повести временны
13736. История отечества. Тест. Вариант 3 128 KB
  Вариант №3 Часть 1 А1. Какое из указанных событий произошло позднее других 1 начало опричнины 3 созыв первого Земского собора 2 Стоглавый собор 4 присоединение Казанского ханства А2. Во гл...
13737. История отечества. Тест. Вариант 4 124.5 KB
  Вариант №4 Часть 1 А1. Что из указанного относится к XII в. 1 приглашение Владимира Мономаха на княжение в Киев 2 походы Святослава на печенегов 3 княжение Ярослава Мудрого 4 борьба Александра
13738. История отечества. Тест. Вариант 5 131 KB
  Вариант №5 Часть 1 А1. Какое из указанных событий произошло раньше других 1 битва на реке Воже 3 Куликовская битва 2 разорение Москвы ханом Тохтамышем 4 Грюнвальдская битва А2. Кто из назва...
13739. История отечества. Тест. Вариант 6 130.5 KB
  Вариант №6 Часть 1 А1. Позже других событий произошло 1 воцарение династии Романовых 3 крещение Руси 2 начало феодальной раздробленности 4 введение опричнины А2. Начало государственности ...
13740. История отечества. Тест. Вариант 7 128.5 KB
  Вариант №7 Часть 1 А1. Позже других событий произошло 1 начало Смутного времени 2 первое упоминание о Москве в летописи 3 установление монголотатарского ига 4 завершение образования Российс
13741. История отечества. Тест. Вариант 9 126 KB
  Вариант №9 Часть 1 А1. Кто из перечисленных князей правил позднее других 1 Игорь Старый 3 Владимир Мономах 2 Василий Темный 4 Александр Невский А2. В Новгородской боярской республике высш
13742. История отечества. Тест. Вариант 10 123 KB
  Вариант №10 Часть 1 А1. Какое из перечисленных событий произошло позднее других 1 битва на Калке 3 первое упоминание о Москве в летописях 2 восстание древлян 4 поход князя Игоря Святославича на половце