22116

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

Лекция

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

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

Русский

2013-08-04

362 KB

25 чел.

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

а)      б)


 

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

7891. Причини, привід та початок Першої світової війни 35.5 KB
  Тема уроку. Причини, привід та початок Першої світової війни. Мета: розкрити причини, привід та початок Першої світової війни розвивати аналітичні вміння при вивченні всесвітньої історії виховувати в учнів зацікавленість до новітнього періоду всес...
7892. Воєнні кампанії 1915-1918 років 19.03 KB
  Тема уроку. Воєнні кампанії 1915-1918 років. Мета: розкрити зміст воєнних кампаній 1915-1918 років розвивати аналітичні вміння при вивченні всесвітньої історії виховувати в учнів зацікавленість до новітнього періоду всесвітньої історії Обладнання:...
7893. Юридична відповідальність 48.5 KB
  Тема. Юридична відповідальність Мета: Розглянути поняття юридична відповідальність, ознаки, види, характеристика розвивати в учнів здатність застосовувати отримані на практиці виховувати в ліцеїстів правову культуру та законослухняність. Обладнанн...
7894. Історія Київської Русі 71 KB
  Історія Київської Русі 1.Київська Русь. Загальна характеристика. За часів князювання Володимира Великого (980-1015 рр.) було завершено формування території Київської Русі. Вона займала територію від Чудського, Ладозького й Онезького озер на пі...
7895. Правопорядок і правопорушення. Юридична відповідальність 57 KB
  Правопорядок і правопорушення Мета: Розглянути правопорядок, законність як важливі суспільно-правові явища, визначити зміст поняття правопорушення та його структуру формувати в учнів позитивну правосвідомість розвивати критичне мислення. Обладнанн...
7896. Правоохоронні органи України 58.5 KB
  Правоохоронні органи України Мета: закріплення знань про правоохоронні органи України, їхню структуру та функції розвиток вміння використовувати на. практиці знання, набуті на уроках з правознавства виховання поваги до органів державної влади (у ц...
7897. Орест Субтельний. Україна: Історія. 3.76 MB
  Орест Субтельний. Україна: Історія. Історія України Ореста Субтельного - ґрунтовний підручник з української історії нерадянського штабу, на якому згодом вчилося не одне покоління вітчизняних студентів. Підручник став справжньою класикою навчально-іс...
7898. Цінності та перспективи християнської моралі 97.16 KB
  Цінності та перспективи християнської моралі Зміст Вступ Поняття християнська мораль,її особливості тасутність Основні моральні цінності Перспективи християнської моралі Висновки Література Вступ Тема роботи,на мо...
7899. Поняття політики. Політика і влада 53 KB
  Поняття політика (від грецького поліс - місто-держава, і похідного від нього - політикос - усе, що повязано з містом — держава, громадянин, управління та ін.) має особливу історію. Загальновизнаною є думка, що цей термін набув поширення під впливом трактату Арістотеля Політика...