22116

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

Лекция

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

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

Русский

2013-08-04

362 KB

20 чел.

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

а)      б)


 

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

33271. Управленческое решение: содержание, виды . Стадии и технологии принятия управленческих решений 68.5 KB
  Классификация управленческих решений Классификационный признак Группы Управленческих решений Степень повторяемости проблемы Традиционные Нетипичные Значимость цели Стратегические Тактические Сфера воздействия Глобальные Локальные Длительность реализации Долгосрочные Краткосрочные Прогнозируемые последствия решения...
33272. Элементы налога на имущество организаций и их характеристика 26 KB
  Элементы налога на имущество организаций и их характеристика. Налог на имущество организаций является наиболее весомым в региональных налогах. Плательщиками налога на имущество являются: организации включая банки и кредитные учреждения в том числе с иностранными инвестициями являющиеся юридическими лицами в соответствии с законодательством РФ; филиалы и другие аналогичные подразделения организаций имеющие отдельный баланс и расчетный счет; организации с иностранными инвестициями иностранные компании фирмы международные объединения и...
33273. Элементы транспортного налога и их характеристика 25.5 KB
  Объектом налогообложения являются транспортные средства подлежащие регистрации в соответствии с постановлением Правительства РФ №938 от 12. Налоговой базой является мощность двигателя которая указана в технологическом паспорте транспортного средства в лошадиных силах или киловаттах мощности. Налог исчисляется в рублях с каждой лошадиной силы киловатта мощности каждого транспортного средства по ставкам. Налог уплачивается раз в год по месту нахождения плательщика или регистрации транспортного средства и зачисляется в территориальный...
33274. Элементы налога на имущество физических лиц и их характеристика 25.5 KB
  Элементы налога на имущество физических лиц и их характеристика. Плательщиками налога на имущество физических лиц являются граждане РФ иностранные граждане и лица без гражданства имеющие на территории РФ в собственности движимое и недвижимое имущество. Объектом обложения являются находящиеся в собственности физического лица недвижимое и движимое имущество которое соответственно можно разделить на две группы: 1. При исчислении налога на недвижимое имущество налогооблагаемой базой является оценочная стоимость имущества которая может быть...
33275. Элементы земельного налога и их характеристика 33.5 KB
  Существует несколько форм платы за землю: земельный налог арендная плата нормативная цена земли. Ежегодным земельным налогом облагаются собственники земли землевладельцы и землепользователи кроме арендаторов. Арендная плата взимается за земли переданные в аренду. Для покупки и выкупа земельных участков в случаях предусмотренных земельным законодательством РФ а также для получения под залог земли банковского кредита устанавливается нормативная цена земли.
33276. Упрощенная система налогообложения индивидуальных предпринимателей на основе патента 29 KB
  Под субъектами малого предпринимательства понимаются коммерческие организации одновременно удовлетворяющие следующим условиям: 1 Доля участия РФ субъектов РФ общественных и религиозных организаций и объединений благотворительных и иных фондов в уставном капитале организации не превышает 25; 2 Доля уставного капитала доля уставного капитала принадлежащая одному или нескольким юридическим лицам не являющимся субъектами малого предпринимательства не превышает 25; 3 Среднесписочная численность организации не превышает предельного...
33277. Единый налог на вмененный доход для отдельных видов деятельности и его характеристика 27 KB
  Единый налог на вмененный доход для отдельных видов деятельности и его характеристика. Данный налог введен для обложения сфер деятельности где преобладают наличные денежные расчеты. Базовая доходность – условная месячная доходность в стоимостном выражении на ту или иную единицу физического показателя характеризующего определенный вид предпринимательской деятельности в различных сопоставимых условиях которая используется для расчета величины вмененного дохода. Корректирующие коэффициенты базовой доходности – коэффициенты показывающие...
33278. Корректирующие коэффициенты и их применение при расчете единого налога на вмененный доход 23 KB
  К3 коэффициентдефлятор соответствующий индексу изменения потребительских цен на товары работы услуги в Российской Федерации Таким образом расчет единого налога на вмененный доход: ЕНВД = БД х Ф х К1 х К2 х В1 В2 х С где БД значение базовой доходности в месяц по осуществлению розничной торговли; Ф физический показатель характеризующий розничную торговлю в каждом месяце налогового периода площадь торгового зала; К1 коэффициентдефлятор; К2 корректирующий коэффициент; В1 фактическое количество дней работы в месяце; В2 ...
33279. Единый сельскохозяйственный налог и его характеристика 27 KB
  Единый сельскохозяйственный налог и его характеристика. Налогоплательщиками признаются организации крестьянские фермерские хозяйства и индивидуальные предприниматели являющиеся сельскохозяйственными товаропроизводителями т. производящие сельскохозяйственную продукцию на сельскохозяйственных угодьях и реализующие эту продукцию в том числе продукты ее переработки при условии что в их общей выручке от реализации товаров работ услуг доля выручки от реализации этой продукции составляет не менее 70. хоз.