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

-

 

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


 

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

21082. ГОСУДАРСТВЕННОЕ И РЫНОЧНОЕ ЭКОЛОГИЧЕСКОЕ РЕГУЛИРОВАНИЕ 91 KB
  Причины рыночной и государственной неэффективности в охране окружающей среды Формирование механизмов реализации экологической политики концепции устойчивого развития а также экологизации экономики может основываться на трех подходах: прямом регулировании связанном с воздействием государства на процессы экологизации экономики рационализации природопользования и охраны окружающей среды нормативноправовые административноконтрольные меры прямое регламентирование и т. Опыт бывшего Советского Союза и стран Восточной Европы...
21083. Структурно-содержательная основа хозяйственного механизма природопользования (природопользования и экологической безопасности, экологизации производства, экологического регулирования) 253.5 KB
  Общие принципы формирования хозяйственного механизма природопользования. Общие принципы формирования хозяйственного механизма природопользования. Основными особенностями сферы природопользования и охраны окружающей среды как объекта управления являются следующие: Инфраструктурный характер продукции данной сферы качества окружающей природной среды ее экосистем и ресурсов и оказываемых ею услуг природоохранных по ресурсосбережению обеспечению экологической безопасности производства и потребления.
21084. Инструменты экополитики и хозяйственного механизма природопользования 265.5 KB
  Классификация инструментов экополитики и хозяйственного механизма природопользования. Классификация инструментов экополитики и хозяйственного механизма природопользования. Обязательные инструменты экополитики обеспечивают нормативноправовое регулирование которые создают прямые ограничения деятельности юридических и физических лиц в форме правил требований стандартов или указывает на разрешенный способ поведения.
21085. Анализ функционирования и развития хозяйственного механизма природопользования 114.5 KB
  Характеристика современного механизма природопользования экологического регулирования. Направления совершенствования существующих инструментов экологического регулирования. Характеристика современного механизма природопользования экологического регулирования. Экономический механизм экологического регулирования рационализации природопользования в Украине находится на стадии становления.
21086. Торговые механизмы национальной экологической защиты 104.5 KB
  Торговля как инструмент экологической защиты В регулировании влияния на экосистемы не последнюю роль играет торговля. Считается что разногласия которые возникают в системе отношений торговля окружающая среда могут быть до определённой меры разрешимы с помощью таких трех основных подходов: воспитательноубеждающий основывается на принципе: делать то что полезно для окружающей природной среды даже если такие действия не удобны для экономического субъекта; запретноштрафной основывается на использовании разного рода экономических...
21087. Экологизация научно-технического прогресса 82 KB
  Общественные и государственные интересы Интересы потребителей Интересы производителей Рынок экологических инноваций Вторичный рынок экологических товаров Первичный рынок экологических разработок Спрос Предложение Спрос Предложение Мотивационный механизм потребления экологических товаров 1 Мотивационный механизм производства экологических товаров 2 Мотивационный механизм внедрения инновационных разработок 3 Мотивационный механизм разработки инновационных проектов 4 Тема 8: Экологизация научнотехнического прогресса...
21088. Розвиток освіти у XIX - на початку XX ст 22.7 KB
  Було затверджено чотири типи шкіл: парафіяльні повітові губернські гімназії університети. Проміжне становище між гімназіями та університетами займали ліцеї яких на Україні було три: Рішельєвський в Одесі з 1817 p. стало заснування на східноукраїнських землях університетів які завдяки загальноєвропейській реформі університетської освіти швидко почали відігравати велику роль у культурному житті в розвитку науки. Перший університет на українських землях у складі Російської імперії засновано 1805 р.
21089. Розвиток науки у XIX - на початку XX ст 20.63 KB
  Всебічно обдарованим і феноменально працездатним був перший ректор Київського університету М. У розвиток філософської та філологічної наук суттєвий внесок зробив перший ректор Харківського університету І. Засновником вітчизняного слов’янознавства був професор Харківського університету І. ректором Харківського університету був Т.
21090. Розвиток літератури у XIX - на початку XX ст 27.79 KB
  Цей бурлескнотравестійний твір є однією з найбільш талановитих переробок поеми римського поета Вергілія в якій автор подав панорамну картину українського народного життя. Обидва письменники були визначними організаторами театрального життя першої половини XIX ст. Поетизація Гоголем українського життя і національного характеру романтичне зображення минулого українського народу сприяли широкому зацікавленню історією та етнографією України збуджували патріотичні почуття і стверджували гуманістичні цінності в українській культурі. Величні...