22116

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

Лекция

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

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

Русский

2013-08-04

362 KB

22 чел.

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

а)      б)


 

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

6397. История философии и ее связь с историческим процессом 99 KB
  История философии и ее связь с историческим процессом Происхождение философии Основные этапы развития европейской философии Особенности развития русской философии Происхождение философии. Философия возникла одновременно в древнейших...
6398. Материя как предмет философского осмысления 66.5 KB
  Материя как предмет философского осмысления Онтология и проблема бытия Проблема материи в истории философии Атрибуты материи Онтология и проблема бытия Одним из центральных разделов философии является онтология - уче...
6399. Сознание как проблема философии 58 KB
  Сознание как проблема философии Основные философские позиции по проблеме сознания Теория отражения. Основные философские позиции по проблеме сознания. Представители объективного идеализма (Платон, Гегель) трактуют сознание, дух как вечное п...
6400. Диалектика как теоретическая система и метод познания 98.5 KB
  Диалектика как теоретическая система и метод познания Исторические типы метафизики и диалектики Системность Детерминизм Развитие Исторические типы метафизики и диалектики Еще с древности люди заметили, что всем предметам и явлениям ми...
6401. Проблема человека в философии 71 KB
  Проблема человека в философии Проблема человека в истории философии Проблема антропосоциогенеза Природа человека Проблема человека является центральной для всей духовной культуры общества, т.к. только через себя мы понимаем окружающий мир, о...
6402. Человеческая деятельность и ее содержание 116 KB
  Человеческая деятельность и ее содержание Освоение и отчуждение. Проблема свободы. Основные способы освоения мира человеком. Познание. Практически-духовное освоение мира Освоение и отчуждение. Проблема свободы. Центральной проблемой...
6403. Общество как предмет философского анализа 71 KB
  Общество как предмет философского анализа. Социальная философия и ее задачи. Основные философские подходы к пониманию общества. Структура общества Социальная философия и ее задачи. В обыденном сознании существует иллюзия непосредственного во...
6404. Философия истории. Движущие силы и субъекты исторического процесса 66 KB
  Философия истории Предмет и задачи философии истории Периодизация истории общества Движущие силы и субъекты исторического процесса Предмет и задачи философии истории Для историка прошлое - это данность, которая находится вне...
6405. Стилі сучасної української літературної мови у професійному спілкуванні 44.27 KB
  Стилі сучасної української літературної мови у професійному спілкуванні План Функціональні стилі української мови та сфера їх застосування. Основні ознаки функціональних стилів. Текст як форма реалізації мовнопрофесійної діяльності (комунікати...