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

-

 

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


 

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

53135. Йоганн Вольфганг фон Гете – виразник ідей Просвітництва. Творчий і життєвий шлях письменника. Образ Фауста у літературі, музиці, малярстві 82.5 KB
  Liebe Freunde! Ich wünsche euch einen wunderschönen Guten Morgen und freue mich euch wiederzusehen. Wir werden heute über die Gestalt des Faust und den Unterstied dieser Gestalt im Werken von Goethe und Puschkin sprechen und wie diese Gestalt des Faust sich in der Musik und Malerei widergespiegelt hat.
53136. Гетьманщина наприкінці ХVІІ - у першій половині ХVІІІ ст 124.5 KB
  Підручники таблиця Іван Мазепа роздатковий матеріал. Мазепа біографія Дискусійний клуб Обери позицію: дати оцінку діяльності І. Мазепа історична постать неоднозначна таємничо загадкова і до цього часу. В літературних творах оспівано його образ...
53137. Гідросфера. Позакласний захід (КВК) з географії для 6 класу 40.5 KB
  ХІД ГРИ Ведучий: Сьогодні ми проводимо географічний КВК під час вивчення теми Гідросфера. Одиниця вимірювання солоності води проміле. На Дніпрі споруджено 6 великих водосховищ які створюють величезний запас води для більш посушливих південних і східних областей України. Значна кількість дніпровської води подається каналами і трубопроводами в південні і східні регіони України з постійним дефіцитом прісної води.
53138. РОЗРОБКА УРОКУ – ГРИ «СВИСТАТИ ВСІХ НАГОРУ!» (УЗАГАЛЬНЮЮЧИЙ УРОК З ГЕОГРАФІЇ У 7 КЛАСІ) 249 KB
  Мета уроку: навчальна: повторити, узагальнити та систематизувати знання учнів з теми «Гідросфера»; вдосконалювати навички та вміння використовувати набуті знання на практиці у нестандартних ситуаціях; підвищити інтерес до вивчення географії за допомогою ігрової форми,
53139. Гідросфера. Узагальнення (урок – гра у 6 класі) 89.5 KB
  Якщо тему добре знаєш То мене ти відгадаєш Запитання: Про що йде мова У яких станах може перебувати вода на Землі Твердому рідкому газоподібному. Запитання: Яке явище описано у вірші Що є основною причиною утворення кругообігу води в природі Енергія Сонця. Запитання: Про які кольорові моря йде мова Жовте Чорне Червоне Біле . Запитання: Яка основна причина океанічних течій ...
53140. Гигиена питания 98.5 KB
  Действующие лица: комиссар полиции мистер Бортоломью инспектор полиции мистер Дрейк миссис Синтия Бабингтон. Мери пожалуйста пригласите ко мне инспектора Дрейка. Входит инспектор Дрейк. Доброе утро инспектор.
53141. Правила виконання ранкової гімнастики. Частини обличчя 106.5 KB
  Мета уроку: Практична: Ознайомити учнів із значенням та правилами виконання ранкової гігієнічної гімнастики; Закріплення рухових дій засобами естафет, рухливих ігор; Вивчення та відпрацювання вживання лексики по темі в усному мовленні; Формування навичок монологічного мовлення, сприйняття на слух іншомовних слів, опису людини за малюнком;
53142. Гімнастика до занять у початкових класах 56.5 KB
  Гімнастика до занять вирішує головним чином виховні та оздоровчі завдання. Щодня виконувані фізичні вправи надають сприятливий вплив на організм сприяють формуванню правильної постави виховують звичку до регулярних занять фізичними вправами. Колективне виконання вправ під час гімнастики до занять дисциплінує організовує і згуртовує учнів.