22116

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

Лекция

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

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

Русский

2013-08-04

362 KB

24 чел.

Лекция 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, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

а)      б)


 

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

18876. Архитекту́ра моде́рна 22.21 KB
  Архитекту́ра моде́рна архитектура арнуво архитектурный стиль получивший распространение в Европе в 1890е 1910е годы в рамках художественного направления модерн. Архитектуру модерна отличает отказ от прямых линий и углов в пользу более естественных природных линий...
18877. Символизм в Русском искусстве рубежа XIX-XX вв. М.А. Врубель 290.82 KB
  Символизм в Русском искусстве рубежа XIXXX вв. М.А. Врубель. Врубель М.А. был предшественником символизма. Личность художника объясняет характерную особенность всего отечественного искусства. Это искусство никогда не полагается на холодный расчёт ума. Оно согрето живым ис...
18878. От Модерна к новой архитектуре. Форма следует функции. Франк Ллойд Райт. Органическая архитектура 28.41 KB
  От Модерна к новой архитектуре. Форма следует функции. Франк Ллойд Райт. Органическая архитектура. Декоративные приемы уже в скором времени перестали привлекать архитекторов модерна. Со временем этот стиль изменяется и в нем начинают преобладать недекорированные объ
18879. Импрессионизм. К.Моне, О.Ренуар, Э.Дега 27.76 KB
  Импрессионизм. К.Моне О.Ренуар Э.Дега. История теория основные представители. К. Моне. Завтрак на траве Дама в саду ― поиски новой манеры развитие пленера. 1874г. ― первая выставка импрессионистов происхождение термина. Бульвар капуцинок. Серии: Вокзал Сен Лазар...
18881. Классицизм во французской живописи XVII - XIXв. Н.Пуссен, Л.Давид, Энгр 26.71 KB
  Классицизм во французской живописи XVII XIXв. Н.Пуссен Л.Давид Энгр. от лат. classicus образцовый художественный стиль и направление в европейском искусстве 17 нач. 19 в. важной чертой которых являлось обращение к наследию античности Древних Греции и Рима как к норме и ид
18882. Романтизм в европейском и русском искусстве XIX в. Т.Жерико, Э.Делакруа, К.П. Брюллов 24.09 KB
  Романтизм в европейском и русском искусстве XIX в. Т.Жерико Э.Делакруа К.П. Брюллов. Развитие романтизма в живописи протекало в острой полемике с приверженцами классицизма. Романтики укоряли своих предшественников в холодной рассудительности и отсутствии движения жи...
18883. Баро́кко 26.29 KB
  Баро́кко характеристика европейской культуры XVII XVIII веков центром которой была Италия. Стиль барокко появился в XVI XVII веках в итальянских городах: Риме Мантуе Венеции Флоренции. Эпоху барокко принято считать началом триумфального шествия западной цивилизации. Баро...
18884. Евангельская тема в русском искусстве XIX века. А.А.Иванов, Н.Н Ге, И.Н.Крамской, В.Д. Поленов 31.82 KB
  Евангельская тема в русском искусстве XIX века. А.А.Иванов Н.Н Ге И.Н.Крамской В.Д. Поленов. Центральной фигурой в живописи середины века был Александр Андреевич Иванов 18061858. Путь А. Иванова никогда не был легким за ним не летела крылатая слава. При жизни его талант цени...