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

а)      б)


 

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

48155. КАПІТАЛ. ВИРОБНИЧІ ФОНДИ ПІДПРИЄМСТВА І ЇХ ОБОРОТ. ЗАТРАТИ, ЦІНИ І ПРИБУТОК ПІДПРИЄМСТВА 55.5 KB
  Затрати виробництва. Капітал це не просто засоби виробництва гроші а виробниче відношення при якому знаряддя праці певні матеріальні блага мінові вартості служать знаряддям експлуатації привласнення частини чужої праці. Затрати капіталіста на придбання засобів виробництва повністю переносяться на новостворений продукт. Постійний капітал бере участь у процесі праці своїм речовим змістом виступає при цьому фактором виробництва споживання вартостей але не бере участі у процесі збільшення вартостей а відповідно не створює додаткової...
48156. ПІДПРИЄМНИЦТВО В АГРАРНІЙ СФЕРІ 58.5 KB
  Аграрне виробництво особлива сфера вкладення капіталу Сільське господарство одна з найважливіших галузей матеріального виробництва в якій створюються матеріальні блага рослинного і тваринного походження для забезпечення населення продуктами харчування а промисловості сировиною. До особливостей сільського господарства належить і надзвичайна роль землі як фактора виробництва. У сільському ж господарстві земля виступає як засіб виробництва оскільки верхній шар ґрунту служить для розміщення рослин у процесі їх відтворення містить воду...
48157. ДЕРЖАВА ТА ЇЇ ЕКОНОМІЧНІ ФУНКЦІЇ 52.5 KB
  Необхідність цілеспрямованого втручання держави в економіку 2. Еволюція економічної діяльності держави 3. Економічні функції держави 4. Необхідність цілеспрямованого втручання держави в економіку Сучасна ринкова економіка неможлива без ефективного механізму її взаємодії з державою органами законодавчої і виконавчої влади.
48158. ФОРМИ СУСПІЛЬНОГО ПРОДУКТУ В ПРОЦЕСІ ВІДТВОРЕННЯ 147 KB
  Суспільне економічне відтворення основане на органічній єдності всіх частин що його утворюють: виробництва розподілу обміну споживання; домогосподарств підприємств галузей економічних регіонів і всього виробництва; продуктивних сил складових його частин і економічних відносин; суспільного виробництва і суспільного споживання. Економічне відтворення суспільства включає в себе такі найважливіші моменти: відтворення суспільного продукту та його конкретних форм; відтворення людського ресурсу як особистісного фактора виробництва та...
48159. РОЗПОДІЛ НАЦІОНАЛЬНОГО ДОХОДУ. СПОЖИВАННЯ І ЗАОЩАДЖЕННЯ 178.5 KB
  Розподіл національного доходу і обєктивні основи формування доходів населення 3. Перерозподіл національного доходу і споживання 4. Сутність місце та роль розподілу в процесі відтворення В економічній літературі розподільні відносини розглядаються в основному через призму розподілу національного доходу.
48160. ЕКОНОМІЧНЕ ЗРОСТАННЯ ТА ЙОГО ЧИННИКИ. ЕКОНОМІЧНІ ЦИКЛИ 79.5 KB
  Зміст і типи економічного зростання. Теорії і моделі економічного зростання 3. Зміст і типи економічного зростання.
48161. ЗАЙНЯТІСТЬ, ВІДТВОРЕННЯ РОБОЧОЇ СИЛИ ТА ЇХ ДЕРЖАВНЕ РЕГУЛЮВАННЯ 171 KB
  Неповна зайнятість і безробіття в механізмі відтворення робочої сили 4. З початку реформування української економіки сама сфера зайнятості зазнала зміни виникли нові сегменти: самозайнятість і часткова зайнятість або інакше приховане безробіття. Таку часткову зайнятість прийнято називати прихованим безробіттям. Якщо внаслідок перевищення пропонування праці над попитом виникає безробіття то вона впливає націни в бік їх зниження до тих пір поки не буде досягнуто рівноваги на ринку праці на рівні повної зайнятості за якої безробіття...
48162. ГОСПОДАРСЬКИЙ МЕХАНІЗМ У СИСТЕМІ РЕГУЛЮВАННЯ СУСПІЛЬНОГО ВИРОБНИЦТВА 53.5 KB
  Державне регулювання суспільного відтворення та його форми 3. Державне регулювання економіки Список використаних джерел: Основи економічної теорії: Підручник За ред. Державне регулювання суспільного відтворення та його форми Ринковий механізм саморегулювання дає можливість: ефективно розподіляти ресурси для виробництва необхідних суспільству товарів; успішно функціонувати за наявності навіть обмеженої інформації досить мати дані про ціну на продукт і про витрати на його виробництво; забезпечувати гнучкість і високий ступінь...
48163. ЗАКОНОМІРНОСТІ ТА ЕТАПИ РОЗВИТКУ КАПІТАЛІСТИЧНОЇ ЕКОНОМІЧНОЇ СИСТЕМИ 82.5 KB
  Економічна система капіталізму вільної конкуренції: сутність і етапи розвитку Капіталізм вільної конкуренції характеризується приватною капіталістичною власністю на речові ресурси використанням найманої праці та системи ринків чистої конкуренції. Проте не існує різних думок щодо таких інститутів капіталізму вільної конкуренції: приватна власність на засоби виробництва; система найманої праці; 3 свобода підприємництва і вибору; ринкова система та вільна конкуренція; важлива роль прибутку; обмежена роль держави. Система найманої...