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

а)      б)


 

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

53262. Свято гумору Хочете жити на втіху, частіше «вмирайте» від сміху 86.5 KB
  Сценка Інтернетце сила Василина Кумонько а куди це ви поспішаєте Параска Як куди На базар поторгувати вирішила. А тепер і результат Василина Кумонько а чим це від вас так тхневідвертається Параска Ойта це ж мої нові духи Запах доярки†називаються. Василина – Ходімо кумонько ходімо будемо дивитись кому гарбуза давати а до кого і на побачення ходити. Сценка Дві кумасі Одна модна друга – не дуже у фуфайці.
53263. Свято гумору і здоров’я 50.5 KB
  Ведучий 1. Добрий день шановні учні вчителі та гості нашого свята Ведучий 2. Вітаємо Ведучий 1. Ми раді новій зустрічі і вітаємо всіх вас на святі гумору Ведучий 2.
53264. Розробка заняття гуртка по темі: Птахи прилетіли 75 KB
  Розширити знання дітей про птахів; ознайомити із сезонними явищами в їхньому житті та особливостями гніздування; вчити дітей вдумливо дбайливо уважно ставитися до оточуючого середовища замислюватись над наслідками своїх дій; Розвиваюча. розвивати уміння порівнювати птахів різних екологічних груп та рядів розпізнавати їх у природі; уміння спостерігати і використовувати набуті знання у повсякденному житті; розвивати цікавість до фауни країни; Виховна. виховувати бережливе ставлення до птахів дикої природи та тих які...
53265. Заняття гуртка математики на тему «Михайло Васильович Остроградський – видатний український математик» 244.5 KB
  Спочатку юний Остроградський вчився неохоче. Поступово Остроградський починає вчитися з величезним захопленням і невдовзі вже дивує свого вчителя успіхами. університет Остроградський рік живе у батька.
53266. Душа – се конвалія ніжна… 89 KB
  Додаток 12 Виступи супроводжуються демонстрацією зображень квітки а також виробів в різних техніках конвалії 2. Обговорення компонентів виробу Дітям пропонується розглянути ілюстрації обговорити в групах та відповісти на питання: Із яких частин складається квітка конвалії Матеріали яких кольорів знадобляться нам для виготовлення квітки 2. Самостійна робота виготовлення панно Конвалія Кожній групі необхідно розподілити обов’язки для виконання роботи: Підібрати паперові смужки та фон; Виготовити елементи квітів;...
53269. РЕШЕНИЕ ЗАДАЧ С ЛОГИЧЕСКИМ СОДЕРЖАНИЕМ 165 KB
  План занятия: Разминка Решение задач Физкультминутка Решение практических задач Самостоятельное решение задач Итог занятия Ход занятия: Разминка проводится в виде устных упражнений на отгадывание чисел. Решение задач Задачи с логическим содержанием требуют систематизации данных в условии. с помощью таблицы с помощью графов На этом занятии мы рассмотрим решение задач с помощью таблиц.
53270. Програма гуртка «Домашні улюбленці» 154.5 KB
  Як правило, діти люблять домашніх тваринок, сприймають їх як своїх друзів. Проте не завжди відчувають відповідальність за своїх маленьких улюбленців, не мають необхідних знань і навчичок правильного догляду за ними. Є категорія дітей, які не мають домашніх тваринок, проте цікавляться тваринним світом, мріють про маленького друга.