22116

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

Лекция

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

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

Русский

2013-08-04

362 KB

24 чел.

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

а)      б)


 

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

44571. Комбинированные сети 46 KB
  На рабочих станциях ЛВС устанавливают Windows NT WorkSttion или Windows 95 98 которые будут управлять доступом к ресурсам выделенного сервера и в то же время предоставлять в совместное использование свои жесткие диски а по мере необходимости разрешать доступ и к своим данным Структура комбинированной ЛВС Комбинированные сети наиболее распространенный тип ЛВС но для их правильной и надежной защиты необходимы определенные знания и навыки планирования. А вот различия между одноранговыми сетями и ЛВС с выделенными серверами существенно...
44572. Понятие топологии сети и базовые топологии 31 KB
  Термин топология сети или просто топология характеризует физическое расположение компьютеров сетевых сред передачи данных и других компонентов сети. Топология это стандартный термин который: используется при описании основной компоновки сети; дает способ сравнивать и классифицировать различные сети. Топология сети обуславливает ее технические характеристики.
44573. Топология типа «шина» 82.5 KB
  В ней используется один сетевой кабель именуемый магистралью или сегментом вдоль которого подключены все РС сети. Пакет в виде электрических сигналов передается по шине в обоих направлениях всем компьютерам сети. Так как в каждый момент времени в сети может вести передачу только одна РС то производительности ЛВС зависит от количества РС подключенных к шине. Чем их больше тем больше ожидающих передачи данных тем ниже производительности сети.
44574. Топология типа «звезда» 65.5 KB
  Основное достоинство этой топологии в том что если повреждена какая-либо РС или отдельное соединение между РС и концентратором вся сеть остается работоспособной. Как недостатки организации такой топологии следует отметить следующее: Так как все РС подключены к центральной точке то для больших ЛВС значительно увеличивается расход кабеля. Концентраторы являются центральным узлом в топологии звезда.
44575. Топология типа «кольцо» 41 KB
  Кроме того изменение конфигурации сети или подключение новой РС требует остановки всей сети.
44576. Комбинированные топологии 66 KB
  Звезда шина strbus - это комбинация топологий шина и звезда Чаще всего это выглядит так: несколько сетей с топологией звезда объединяются при помощи магистральной шины. Топология €œзвезда-кольцо Звезда-кольцо strring кажется похожей на звезду-шину И в том и в другом случае компьютеры подключены к концентратору который фактически формирует кольцо или шину.
44577. Сравнительные характеристики топологий 31.5 KB
  При значительных объемах трафика уменьшается пропускная способность; трудная локализация проблем; выход из строя кабеля остановит работу пользователей. выход из строя одной РС выводит из строя всю сеть; трудно локализовать проблемы; изменение конфигурации сети требует остановки всей сети. Звезда легко модифицировать сеть добавляя новые РС; централизованный контроль и управление; выход из строя РС не влияет на работу сети. Выход из стоя центрального концентратора выводит из стоя всю сеть.
44578. Методы доступа, Коллизия в сети 87 KB
  Коллизия в сети Наибольшее распространение при проектировании и построении ЛВС получили два метода доступа зто: Множественный доступ с контролем несущей и обнаружением коллизии CSM CD CrrierSense Multiple ccess nd Collision Defection. Алгоритм работы рабочей станции а точнее ее сетевого адаптера при использовании первого метода доступа заключается в следующем: 1. Вдумайтесь в название этого доступа.
44579. Типы и компоненты беспроводных сетей 30 KB
  В зависимости от технологии беспроводные сети подразделяют на: локальные вычислительные сети; мобильные вычислительные сети. Их можно устанавливать как на автономно работающих компьютерах так и на компьютерах подключенных к сети. Трансивер - это устройство для подключения компьютера к сети т.