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

-

 

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


 

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

70822. Измерения активного сопротивления 564.5 KB
  Получение навыков измерения активного сопротивления. Ознакомление с методами измерения активного сопротивления. Ознакомьтесь с принципами организации измерения активного сопротивления косвенным методом.
70823. УПРОЩЕННАЯ ПРОЦЕДУРА ОБРАБОТКИ РЕЗУЛЬТАТОВ ПРЯМЫХ ИЗМЕРЕНИЙ С МНОГОКРАТНЫМИ НАБЛЮДЕНИЯМИ 401 KB
  Ознакомление с упрощенной процедурой обработки результатов прямых измерений с многократными наблюдениями. Знакомство с методами планирования количества наблюдений получение навыков обработки результатов наблюдений и оценивания погрешностей результатов измерений.
70824. Исследование модели шинной ЛВС со случайным доступом 134.5 KB
  Исследовать особенность построения и функционирования шинной ЛВС со случайным методом доступа и определение основных характеристик сети. В результате выполнения лабораторной работы получены знания по структуре, форматам кадров и протоколам физического и канального уровней...
70825. Изучение параметров сигнала с помощью программы SpectrLAB 4.08 MB
  Записать с помощью предоставленного микрофона звуковой сигнал определенной длительности. Изучить его параметры с помощью программы SpectraLAB v4.32.8. Выполнение задания: Исходный сигнал записан в звуковом формате wav, со следующими параметрами: Длительность: 5.28 с...
70827. Дослідження аналогової інтегральної мікросхеми 597 KB
  Експериментальне визначення параметрів не потребує знання схеми і може бути здійснено як для будь-якого чотириполюсника шляхом вимірювання струмів і напруг вхідного і вихідного сигналів.
70828. Счетчик импульсов 130 KB
  Цель: исследование работы счетчика импульсов. Приборы: модель счетчика импульсов СИ блок питания на 5В БП5 соединительные провода. Подсоединить провода питания 5В к выходу БП5 и к входу модели счетчика импульсов СИ. Однократным нажатием на кнопку Счет прибора СИ подаем импульс на вход счетчика.
70829. Децимация и интерполяция 104 KB
  Выполнение процедуры децимации (уменьшения частоты дискретизации в заданное целое число раз) приводит к уменьшению частоты дискретизации исходной последовательности. В процессе децимации исходная последовательность обрабатывается НЧ фильтром, после чего производится выборка с необходимой частотой.
70830. Функции реализуемые АЛУ 112 KB
  Изучить назначение и состав узла АЛУ на примере ИМС К155ИПЗ и К 561 ИПЗ. В состав различных серий микросхем лежащих в основе МП входят стандартные узлы арифметическо-логических устройств АЛУ например К 155 ИПЗ К 561 ИПЗ. Кроме того имеются вход Р0 и выход Р сигналов переноса...