22118

Абстрактный синтез конечных автоматов

Лекция

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

Составить аналогичную таблицу описывающую работу конечного автомата не представляется возможным т. множество допустимых входных слов автомата вообще говоря бесконечно. Мы рассмотрим один из возможных способов формального задания автоматов а именно задание автомата на языке регулярных событий. Представление событий в автоматах.

Русский

2013-08-04

25.5 KB

11 чел.

Лекция 4

Абстрактный синтез конечных автоматов.

При синтезе комбинационных схем можно составить таблицу зависимости значения выходного сигнала от комбинации входных. Такая таблица однозначно определяет систему ПФ, описывающую работу КС.

 Составить аналогичную таблицу, описывающую работу конечного автомата, не представляется возможным, т.к. множество допустимых входных слов автомата, вообще говоря, бесконечно. Поэтому для задания КА и используются таблицы переходов и выходов, которые позволяют представить соответствие между бесконечными множествами входных и выходных слов конечными таблицами. В связи с этим, прежде чем приступить к синтезу схемы КА необходимо составить таблицу переходов и выходов, что не всегда является простым делом особенно в тех случаях, когда алгоритм работы автоматов задан в описательной форме. Для того, чтобы упростить и формализовать процедуру построения таблиц переходов и выходов необходимо ввести такую исходную форму задания автоматов, переход к которой от алгоритмов, сформулированных в описательной форме, не представляет трудностей. Мы рассмотрим один из возможных способов формального задания автоматов, а именно, задание автомата на языке регулярных событий.

Представление событий в автоматах.

В основе рассматриваемого  способа задания автоматов, лежит понятие событий, представимых в автоматах.

 Определение. Событием называют любое множество слов входного алфавита X {x1, x2, …,xm} автомата.

Пусть Y{y1, y2, …, yk} – выходной алфавит конечного автомата S с фиксированным начальным состоянием a0. Тогда каждой букве yj, выходного алфавита можно поставить в соответствие множество входных слов Sj(x1, x2,…, xm), которые вызывают появление на выходе автомата буквы yj. Определенное таким образом множество слов Sj(x1, x2, …, xm) называют событием, представленным в автомате выходным сигналом yj.

Поэтому для задания конечного автомата, имеющего выходной алфавит Y{y1, y2, …, yk}, достаточно разбить множество всех возможных входных слов на K событий S1, S2, …, Sk, представленных в автомате выходными сигналами y1, y2, …, yk соответственно. Для частичного автомата необходимо, кроме того, задать множество Sз запрещенных слов. Таким образом, конечный автомат может быть задан таблицей, устанавливающей соответствия между событиями и буквами выходного алфавита. Зная набор событий Sj, можно, не пользуясь таблицами переходов и выходов, найти реакцию автомата на любое входное слово, для чего достаточно определить в множество каких слов входного алфавита оно входит (т.е. какому событию принадлежит).

Событие

буква выходного алфавита

S1(x1, x2,…, xm)

S2(x1, x2,…, xm)

Sk(x1, x2,…, xm)

S(x1, x2,…, xm)

y1

y2

yk

-

 

 Для описания автоматов на языке регулярных событий вводят ряд операций над событиями, т.е. строят алгебру событий. Мы рассмотрим алгебру событий, введенную Клини и усовершенствованную академиком Глушковым В. М.


 

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

35181. ОПЕРАЦИОННЫЕ СИСТЕМЫ И СРЕДЫ 2.18 MB
  Обычный урок В начале урока проверка Д З в виде контрольной работы или устного ответа и конспектов Вопросы для подготовки к экзамену по дисциплине Операционные системы Основные понятия и определения ОС. Ресурсы вычислительной системы их классификация. Управление оперативной памятью вычислительной системы.
35182. Информатика и сетевое администрирование 232 KB
  Узел составной сети имеющий IPадрес называется хост host. Локальный адрес это адрес присвоенный узлу в соответствии с технологией подсети входящей в составную сеть. IPадрес состоит из двух логических частей номера подсети ID подсети и номера узла ID хоста в этой подсети. При передаче пакета из одной подсети в другую используется ID подсети.
35183. Правовые информационные системы. ПИС 174 KB
  В чем состоит официальное опубликование документа Под официальным опубликованием НПА следует понимать помещение полного текста документа в специальных изданиях признанных официальными действующим законодательством. Как получить доступ к правовым документам регионов России Для профессиональной деятельности наряду с федеральным законодательством необходимы и акты субъектов Федерации. Это существенно более простые по сравнению с профессиональными системами продукты позволяющие пользователям Интернет при необходимости ознакомиться с...
35184. Проблема первоначала у представителей идеализма в античности 74 KB
  Изложите учения о первоначале в философии античных атомистов Какое значение имело это учение в истории развития философии и науки 1. В истории философии материализм как правило был мировоззрением передовых классов и слоев общества заинтересованных в правильном познании мира в усилении власти человека над природой. Первые учения материалистов появились вместе с возникновением философии в рабовладельческих обществах древней Индии Китае и Греции за несколько веков до н.Исходной точкой развития античной философии был философский...
35185. Сопоставьте особенности буржуазных революций в США и Японии. Как решался аграрный вопрос в США и почему он оказался не под силу Японии 69 KB
  Процесс огораживания лишал земли английских крестьян которые искали потерянную землю за океаном. Владелец земли не мог уследить за тем кто проживает на его территории так как она была слишком велика и владелец проживал в Англии. 2 В средней группе колоний расположенных в зоне прерий развивается сельское хозяйство фермерского типа так как земли были очень плодородные. Первая группа противоречий касалась земли.
35186. Реформы Александра II и отмена крепостного права 68 KB
  Происходит заметное оживление либерально-оппозиционного движения среди тех слоев дворянства, которые считали необходимым не только отменить крепостное право, но и создать общесословные выборные органы управления, учредить гласный суд, ввести гласность вообще, провести преобразования в сфере просвещения и т. д.
35187. СССР в период «перестройки» (1985-1991 гг.) 81.5 KB
  Архангельске Контрольная работа по дисциплине: История отечества На тему: СССР в период перестройки 19851991 гг. в России как и в целом СССР стали происходить серьёзные изменения. СССР в период перестройки В марте 1985 года после смерти К. Руководство взяло курс на активизацию внутренний и внешний политики СССР на восстановление и укрепление авторитета партии и государственной власти внутри общества и на международной арене.
35188. Культура Киевской Руси 117 KB
  Материальная и духовная культура. Культура Киевской Руси. Смысл и назначение культуры и культурологии Слово культура является одним из наиболее употребляемых оно знакомо каждому из нас но мало кто возьмется объяснять что такое культура с теоретической и научной точки зрения. У большинства людей культура ассоциируется с воспитанностью образованностью интеллигентностью.
35189. Зарождение культуры на Руси 126 KB
  Культура Руси складывается в те же века что и зарождение государства. Особенность Руси в том что она складывалась и развивалась на достаточно большой территории где жили различные племена: поляне северяне радимичи и мног. В связи с этим славянская культура имеет свои региональные черты одни для Поднепровья другие для Северо Восточной Руси и т.