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

-

 

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


 

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

54770. ХИМИЧЕСКАЯ АЗБУКА ПИЩИ 186 KB
  Задача устно В куске белого пшеничного хлеба 08 мг железа. Тема урока: Железо его свойства нахождение в природе Цели урока: Знать положение железа в периодической системе Д. Менделеева нахождение железа в природе свойства железа. Уметь объяснять суть химических реакций с точки зрения окислительно восстановительной теории обосновывать необходимость получения железа из руд.
54772. Общее недоразвитие речи 30.5 KB
  Познакомить учащихся с документацией, необходимой для обследования детей с ОНР. Развивать практические навыки и умения у учащихся при частичном обследовании детей с ОНР. Формировать интерес к профессии логопеда и воспитывать гуманное отношение к детям с тяжелыми нарушениями речи.
54773. ЖИЗНЬ В ОКЕАНЕ 178 KB
  Продолжить формирование представлений и знаний о Мировом океане. Познакомить учащихся с особенностями и условиями жизни в океане с разнообразием его обитателей и их распределением и распространением. Оборудование: карта полушарий или карта Мирового океана книги видеофильм Жизнь в Океане таблицы рисунки доклады учащихся.
54774. Безработица 52 KB
  Основные понятия: безработица рабочая сила рынок труда естественная безработица фрикционная институциональная добровольная вынужденная структурная региональная циклическая скрытая частичная уровень безработицы полная занятость.
54775. Греческие колонии на берегах Средиземного и Чёрного морей 94 KB
  Этот период называют Великой греческой колонизацией временем когда греки активно осваивали новые земли и основали множество колоний. Нам предстоит сегодня выяснить: Что дала грекам колонизация т ответить навопросы слайд 2 Далее учитель обращается к учащимся с вопросом...
54776. ОРГАНИЗАЦИЯ ФИЗИЧЕСКОГО ВОСПИТАНИЯ В ОБЩЕОБРАЗОВАТЕЛЬНЫХ УЧРЕЖДЕНИЯХ 126 KB
  Физкультурные минуты во время уроков; физические упражнения и подвижные игры на удлиненных переменах; ежедневный час здоровья в группах продленного дня; занятия ритмикой.; группы общей физической подготовки; б общешкольные физкультурно-массовые и спортивные мероприятия...