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

-

 

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


 

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

72489. Сердечно – легочная реанимация 63.5 KB
  Обеспечить проходимости дыхательных путей: освободить полость рта и глотки от инородных масс кровь слизь рвотные массы зубные протезы жвачка рукой обернутой салфеткой платком предварительно повернув голову спасаемого набок.
72490. Введение лекарственных средств 79 KB
  Перед инъекцией кожу протирают стерильным шариком смоченным 70 раствором спирта левой рукой собирают ее в складку треугольной формы основанием вниз правой рукой берут шприц и придерживая иглу и поршень быстрым движением вкладывают иглу в основании треугольника под углом 45 на глубину 12 см.
72491. ПМП при острых заболеваниях брюшной полости, почечной колике 92 KB
  Возникает рвота кишечным содержимым имеющим неприятный каловый запах. Местный перитонит возникает при отграничении участка воспаления спайками петлями кишечника; локализуется вблизи источника воспаления желчный пузырь червеобразный отросток. Возникает в результате воспалительных процессов в матке или придатках.
72492. Раны. Кровотечения 101.5 KB
  Рана – механическое нарушение целостности кожи, слизистых оболочек с повреждением глубинных тканей. Основные признаки раны: боль – наиболее выражена в местах с наибольшим количеством нервных окончаний (кончиках пальцев, надкостница, плевра). кровотечение – абсолютный признак раны.
72493. Первая медицинская помощь при травмах 79 KB
  Травма (от греч. trаuma — рана) — повреждение тканей организма человека с нарушением их целостности и функций, вызванное механическими или иными воздействиями (например, вывихи, растяжения, переломы). Травматология – наука о травмах и их лечении.
72494. Упражнение в свободе 69 KB
  Это не расхожая мораль: поблудил покайся вернись; или слезная история возвращения неузнанного сына столь любезная чувствительным сирийцам дар слезный в противовес египетской памяти смертной а что-то совершенно поразительное: поражающее как молния аз есмь Этот опыт себя в истории философии и в жизни...
72495. Філософсько-теоретичні основи історії української культури 56.5 KB
  У середні віки набуває поширення комплекс значень згаданого слова, згідно з яким культура стала асоціюватися з міським укладом життя, а пізніше, в епоху Відродження, — з досконалістю людини. Нарешті, у XVIII ст. слово культура набуло самостійного наукового значення.
72496. Історичні умови виникнення та джерела формування української культури 58.5 KB
  Жоден фактор, що визначає нації сучасного світу, не може пояснити самобутність кожної національної культури. Тільки у неповторному комплексі природних, расово-етнічних, мовних та геополітичних факторів, що діяли в конкретному історичному часі, й формувалися народи теперішнього світу...
72497. Понятие, предмет и задачи социально-экономической статистики 508 KB
  Статистика населения Статистика населения решает задачи по изучению численности населения движения населения уровня доходов и расходов населения и уровня неравенства населения в разрезе различных территорий. Данные о численности населения берутся по данным переписи населения.