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

-

 

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


 

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

85380. Распространение загрязняющих веществ 64 KB
  Если выбрасываемые в воздух примеси состоят из крупных частиц то распространяясь в атмосфере они под действием силы тяжести начинают спускаться с определенной постоянной скоростью в соответствии с законом Стокса. Естественно что почти все примеси в конечном итоге осаждаются на поверхности земли причем тяжелые осаждаются в основном под действием гравитационного поля а легкие в результате диффузионного процесса. Поскольку наиболее опасны для окружающей среды примеси газообразного вида типа окислов то именно таким легким соединениям...
85381. Нормирование качества воздуха, воды, почвы 67.5 KB
  Совершенно недопустимо сравнивать уровни загрязнения селитебной зоны с установленными ПДКрз а также говорить о ПДК в воздухе вообще не уточняя о каком нормативе идет речь. Уровень загрязнения атмосферы обычно описывается набором статических характеристик для ряда измеряемых вредных веществ. Для оценки степени загрязнения атмосферы средние максимальные концентрации веществ нормируются на величину средней максимальной концентрации для большого региона или на санитарногигиснический норматив ПДК. Нормированные характеристики загрязнения...
85382. Организация экоаналитического контроля 53 KB
  Контролируемые объекты и компоненты в экоаналитическом контроле Организация и обеспечение ЭАК требуют решения комплекса взаимосвязанных проблем которые образуют приведенную ниже единую систему: Нормативнотехническое обеспечение и правовая регламентация Контролируемые объекты и компоненты Методическое обеспечение Аппаратурное обеспечение Метрологическое обеспечение Обеспечение качества химической информации Кадровое обеспечение Нормативнотехническое обеспечение и правовая регламентация системы ЭАК С точки зрения природоохранительного...
85383. Требования к средствам измерения и классификация экоаналитических средств 35.5 KB
  Требования к средствам измерений Различными нормативными документами в области обеспечения единства измерений предъявляется достаточно жесткие требования к средствам измерений СИ применяемым при экоаналитических работах. Прежде всего СИ должны пройти испытания с целью утверждения типа средств измерений. После получения положительного результата испытаний такие средства измерений включаются в установленном порядке в Государственный реестр средств измерений При эксплуатации СИ необходимо соблюдать установленную в техническом паспорте СИ...
85384. Система наблюдения и контроля атмосферного воздуха ОГСНКа 34 KB
  В России существует сеть станций которая ведет наблюдения за содержанием загрязняющих веществ в атмосфере. Обычно на каждом посту измеряется до 8 загрязняющих веществ но учитывая что каждый промышленный центр имеет свою экологическую специфику и набор 3В возможно измерение до 80 компонентов. Стационарный пост предназначен для обеспечения непрерывной регистрации содержания загрязняющих веществ или регулярного отбора проб воздуха для последующего анализа. Помимо наблюдений в городах ведутся наблюдения за пределами урбанизированных...
85385. Средства контроля воздушных и других газообразных сред 81 KB
  Отбор проб воздуха. Средства контроля подразделяют на: системы комплексы приборы другие технические средства контроля загрязнения ТСКЗ воздушного бассейна с группировкой их по особенностям анализируемой воздушной среды следующим образом: ТСКЗ атмосферы ТСКЗ воздуха населенных мест и жилых помещений ТСКЗ воздуха рабочей зоны и производственных помещений ТСКЗ выбросов и паро воздушных смесей поступающих в атмосферу. Они могут быть сгруппированы следующим образом: промышленные газоанализаторы более 60 40 анализаторы...
85386. Экологический мониторинг поверхностных водных объектов 78.5 KB
  Программа ГСМОС Вода включает 7 основных пунктов: создание всемирной сети станций мониторинга; разработка единой методики отбора и анализа проб воды; осуществление контроля за точностью данных; использование современных систем хранения и распространения информации; организация повышения квалификации для специалистов; подготовка методических справочников; обеспечение необходимым оборудованием в отдельных случаях. Основные задачи систематических наблюдений за качеством поверхностных вод в системе ОГСНК можно сформулировать следующим образом:...
85387. Отбор проб воды. Методы анализа водных сред 47.5 KB
  Отбор проб воды. representtive представительный показательный считается такая проба которая в максимальной степени характеризует качество воды по данному показателю является типичной и не искаженной вследствие концентрационных и других факторов. Пробы из рек и водных потоков отбирают для определения качество воды в бассейне реки пригодности воды для пищевого использования орошения для водопоя скота рыборазведения купания и водного спорта установления источников загрязнения. Учитывая длительность существования озер на первый план...
85388. Роль пробоотбора в общей процедуре методики анализа 44.5 KB
  Роль пробоотбора в общей процедуре методики анализа. Отбор проб почвы донных отложений растительности. Эффективность и достоверность методик и методического обеспечения системы экоаналитического контроля определяются прежде всего пробоотбором и пробоподготовкой. Любой химический анализ чаще всего начинают с отбора и подготовки пробы к анализу.