22116

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

Лекция

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

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

Русский

2013-08-04

362 KB

23 чел.

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

а)      б)


 

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

11345. ФИНАНСОВЫЕ УСЛУГИ НА РЫНКЕ ЗАЕМНОГО КАПИТАЛА 211 KB
  26 Тема 5 ФИНАНСОВЫЕ УСЛУГИ НА РЫНКЕ ЗАЕМНОГО КАПИТАЛА План 1. Критерии выбора кредитных услуг: 1.1. Классификация кредитных операций в соответствии с типом заемщика. 1.2. Классификация кредитных операций по срокам. 1.3. Классификация кредитных оп
11346. ФИНАНСОВЫЕ УСЛУГИ НА ФОНДОВОМ РЫНКЕ 316.5 KB
  42 Тема 6 ФИНАНСОВЫЕ УСЛУГИ НА ФОНДОВОМ РЫНКЕ План 1. Финансовые инструменты фондового рынка. 2. Особенности биржевого обращения ценных бумаг. 3. Расчетноклиринговые учреждения. 4. Финансовоэкономические показатели применяемые на фондовом ры...
11347. Строение и свойства металлов. Аллотропия (полиморфизм). Анизотропия. Кристаллизация. Дендрит, зерно. Строение стального слитка. Ликвация 496.72 KB
  Лекция 1. Введение. Строение и свойства металлов. Аллотропия полиморфизм. Анизотропия. Кристаллизация. Дендрит зерно. Строение стального слитка. Ликвация. Строение и свойства металлов. Все вещества в зависимости от температуры и давления могут находиться в тр
11348. Основы теории сплавов. Типы сплавов (твердые растворы, сплавы-смеси, сплавы- химические соединения. Диаграммы состояния сплавов, принцип их построения 158.57 KB
  Лекция 2 Основы теории сплавов. Типы сплавов твердые растворы сплавысмеси сплавы химические соединения. Диаграммы состояния сплавов принцип их построения. Сплавы – важные вещества получаемые сплавлением или спеканием двух или нескольких элементов периодическ...
11349. ДИАГРАММА ЖЕЛЕЗО-УГЛЕРОД (ЦЕМЕНТИТ). Компоненты, фазы и структурные составляющие железоуглеродистых сплавов 95.23 KB
  Лекция 3 ДИАГРАММА ЖЕЛЕЗОУГЛЕРОД ЦЕМЕНТИТ. Компоненты фазы и структурные составляющие железоуглеродистых сплавов. Железоуглеродистые сплавы – стали и чугуны являются основными наиболее распространенными среди материалов используемых в различных отраслях
11350. Критические точки сталей. Классификация и свойства углеродистых сталей 48.28 KB
  Лекция 4 Критические точки сталей. Классификация и свойства углеродистых сталей. Большинство технологических операций термическая обработка обработка давлением и др. проводят в твердом состоянии. Ниже рассматриваются превращения протекающие в сталях при охла
11351. Классификация и свойства чугунов 137.79 KB
  Лекция 5 Классификация и свойства чугунов Чугунами называются железоуглеродистые сплавы содержащие более 214 углерода и согласно диаграммы железоцементит затвердевают с образованием эвтектики. Благодаря хорошим литейным свойствам достаточной прочности износо...
11352. Термическая обработка сталей 98.15 KB
  Лекция 6 Термическая обработка сталей. Термической обработкой называется технологический процесс включающий нагрев стали до определенной температуры выдержку при этой температуре и охлаждение с необходимой скоростью. Целью термической обработки является получе...
11353. Термическая обработка. Превращения при непрерывном охлаждении аустенита. Превращения при отпуске 65.7 KB
  Лекция 7 Термическая обработка. Превращения при непрерывном охлаждении аустенита. Превращения при отпуске. Превращение переохлажденного аустенита можно осуществить в изотермических условиях т.е. при постоянной температуре и при непрерывном охлаждении. Изотермиче...