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

-

 

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


 

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

28004. Формирование биогенной нагрузки в природных аграрных системах. Естественные потери биогенных веществ в земледелии, животноводстве и селитебных территорий 4.24 KB
  Естественные потери биогенных веществ в земледелии животноводстве и селитебных территорий. Интенсивно развивающееся сельское хозяйство это наиболее активный источник поступления биогенных элементов. Влияние с х как источника поступления биогенных веществ в природные ресурсы возрастает в связи с увеличением распаханности территорий трансформацию угодий мощной техникой развитием процессов химизации на основе минеральных и органических удобрений. Потери биогенных веществ в растениеводстве условно можно разделить на...
28005. Функционирование агроэкосистем в условиях техногенеза 4.85 KB
  Функционирование агроэкосистем в условиях техногенеза. Агроэкосистема АЭС совокупность биогенных и абиогенных компонентов участков суши преобразованных человеком используемых для производства сельхозпродукции. Основа АгроЭкоСистем почва с х угодия. Типы АгроЭкоСистем: Пропашное земледелие Многолетнее земледелие Многоурожайное земледелие МезоАЭС крупномасштабная МикроАЭС грядка Суша занимает площадь 149 млрд.
28006. Экологизация сельскохозяйственного производства 4.56 KB
  Природоразрушающий ресурсоемкий тип развития АПК требует пересмотра сложившейся теории и на практике техногенной концепции развития АПК. Главным принципом развития АПК должна стать экологизация с х производства всех мероприятий по развитию с х учет природных особенностей функционирования земельных ресурсов. для изменения приоритетов в распределении ресурсов капитальных вложений в АПК усилить природоохранную роль затрат. Для преодоления негативных тенденций в развитии АПК скорейшего решения...
28007. Экологическая биотехнология. Возможности увеличения производства экологически безопасной продукции на основе биопроизводства 2.52 KB
  Возможности увеличения производства экологически безопасной продукции на основе биопроизводства. Среди новых направлений биотехнологии способствующих получению экологически безопасной продукции следует отметить применение микробиологических удобрений промышленную переработку бытовых отходов индустриальную технологию компостирования отходов животноводства и др. микробиологические удобрения повышают продуктивность растений и кол во растительной продукции. Азотфиксирующие микроорганизмы служат прекрасной основой для...
28008. Экологически безопасные технологии и оптимизация обработки почвы 3.73 KB
  Поэтому нужна разработка таких сельскохозяйственных машин и орудий которые при общей эффективности должны оказывать минимальный вред окружающей среде а именно: Сократить выбросы от с х машин и орудий Уменьшить нагрузку на почву путем изменения конструктивной особенности техники Внедрение двигателей с высоким КПД но низким потреблением топлива.
28009. Экологические аспекты применения сточных вод при орошении. Ценность сточных вод в повышении плодородия почв. Контроль загрязнения почв 12.86 KB
  Ценность сточных вод в повышении плодородия почв. Сточные воды используются для орошения на специальных участках земледельческих полях орошения ЗПО. Под последними понимаются водохозяйственные объекты оборудованные для непрерывного приема определенного количества сточных вод в течение всего года с целью их очистки или доочистки и использования для орошения.
28010. Экологические особенности и значимость биогумуса. Препараты получаемые на основе биогумуса. Экологические аспекты подготовки и применения биогумуса 2.93 KB
  Препараты получаемые на основе биогумуса. Экологические аспекты подготовки и применения биогумуса. Установлена возможность биогумуса связывать радионуклиды находящиеся в почве органических удобрений резко уменьшать поступление тяжелых металлов в растения.
28011. Экологические проблемы мелиорации. Виды и целевое назначение современных мелиораций. Положительные и отрицательные изменения в ОС под влиянием гидротехнических мелиораций 4.85 KB
  К этим мероприятиям относятся: Орошение и обводнение Осушение земель Противоэрозионные мероприятия закрепление оврагов сыпучих песков почво и полезащитное лесонасаждение. Рассоление почв Выравнивание микрорельефа и т. Мелиорация земель призвана способствовать получению высоких и стабильных урожаев повышению плодородия почв рациональному использованию земельных ресурсов. Орошение способ повышения продуктивности почв важнейшее направление интенсификации с х производства.
28012. Экологические проблемы механизации. Влияние средств механизации на почвенно- биотический комплекс, воздушную среду 14.46 KB
  В результате неоднократного передвижения машин по полю происходит значительное переуплотнение почвы которое распространяется на большую глубину до 100 см а машинные следы покрывают до 80 поля. Докучаева плотность почвы возросла к настоящему времени на 20. Угнетение активности почвенных микроорганизмов переуплотненные почвы и нарушение ее структуры снос перемолотой почвы водой и ветром т. машинная деградация почвы все это отрицательные последствия воздействия на пашню ходовых систем и рабочих...