Автоматные отображе- ния. Теорема Клини
Задавать таблицами соответствия «вход - выход» автоматные отображения чаще всего нельзя, так как обычно мы имеем дело с последовательностями бесконеч- ной длины. Удобной формой задания автоматных отображений является за- дание с помощью событий.
Пусть X = (X0 , X1 , ... XN-1) алфавит, а ется событие в алфавите Х. Событием, представленным в автомате выходным сигналом Yj , называется множество всех слов из Е, отображения на которые, индуцируемые автоматом, оканчивают- ся Yj .
Алгебра событий в алфавите Х - это множество всех событий в этом ал- фавите, на котором заданы операции дизъюнкции, произведения и итера- ции.
Дизъюнкция событий R Ú Q - это собы- тие , состоящее в объединении событий R и Q. Пример R = (X0 , X1X0 ) Q = (X1 , X1X0X1) R Ú Q = (X0 , X1X0 , X1 , X1X0X1)
Произведение событий R×Q - это собы- тие, состоящее из всех слов вида r×q, где rÎR а qÎQ. (К любому слову из R спра- ва приписывается любое слово из Q). Произведение некоммутативно: R×Q ¹ ¹ Q×R.
Пример R = (X0 , X1X0 ) Q = (X1 , X0X1) R×Q=(X0X1, X0X0X1, X1X0X1, X1X0X0X1) Q×R=(X1X0, X0X1X0, X1X1X0, X0X1X1X0)
Итерация события {R} - это событие, состоящее в объединении событий Пример R = (X0 , X1X0 ) {R} = (e, X0 , X1X0, X0X0, X0X1X0, X1X0X1X0, , X1X0X0, X0X0X0, ...)
В алгебре событий выделим регулярныевыражения: 1. X0 , X1 , ... XN-1 и е -регулярные выражения. 2. Если R и Q - регулярные выражения, то R Ú Q, R× Q и {R} тоже регулярные выражения. Регулярно выражение из Х (и только такое), ко-торое получается конечным числом правил 1 и 2.
Для указания порядка выполнения опе- раций в алгебре событий используются скобки (). Одно и то же событие может выражать- ся разными формулами. Например,
Регулярные выражения можно преобра- зовывать, используя свойства операций, вытекающие из их определения. Например: RÚQ = QÚR R×{R} = {R}×R RÚ{R} = {R} {{R}} = {R} RÚe=R PRÚPQ =Р×(RÚQ) R×e = e×R = R PQÚRQ = (PÚR)×Q
Те события, для которых существуют регулярные выражения, называются регулярными событиями. Рассмотрим примеры регулярных событий в алфавите X = (X0, X1, X2).
1. Универсальное событие: 2. Событие из всех двухбуквенных слов: 3. Событие из всех слов, заканчивающихся на X0X2X1 :
4. Событие из всех слов четной длины: 5. . . .
События могут быть нерегулярными (естественно, при бесконечной длине). Покажем это на примере события Т из всех слов алфавита Х длиной n1,n2, ... , ni, ... при i = 1,2, ... i, ... где ni = (i)2.
Пусть Т имеет регулярное выражение. Так как Т бесконечное событие, то его выражение содержит итерацию. Найдем внешнюю итерацию, не входящую в другие. Тогда Т может иметь вид Т = = Р×{T1}×QÚ... , где P и Q - любые регу- лярные выражения.
Отсюда следует, что в Т входят слова, образованные из P×Q,P×T1×Q,P×T1×T1×Q,... Длины этих слов образуют арифмети- ческую прогрессию, а числа n1,n2, ... ,ni, ... при ni = (i)2 - не образуют.
\Т - нерегулярное событие.
Что касается регулярных событий, то теорема доказанная Клини утверждает: класс событий, представимых в ко- нечных автоматах, совпадает с клас- сом регулярных событий.
Любое регулярное событие может быть представлено автоматом Мура. Автомат, представляющий событие Ei , распозна- ет входную последовательность и пере- ходит в состояние, отмеченное yi , если последний символ входной последова- тельности завершает цепочку символов, образующих слово из Ei .
Каждое состояние автомата должно идентифицировать входные последо- вательности, приводящие в него так, чтобы была возможность однозначно продолжать распознавание входной последовательности как начальной части слов из Ei .
Если входная последовательность не является словом из Ei , то она может являться начальной частью одного или нескольких слов из Ei . Пример Ei = (X1X2X0, {X0}X1X2X1, ... ) Входная последовательность X1X2 мо- жет быть началом 2-х слов из Ei .
Теорема Клини определяет возможнос- ти автоматов, ограничивая их отобра- жениями конечной длины, либо беско- нечными, включающими фиксирован- ные последовательности конечной дли- ны или периодически повторяющиеся.
Структурные автоматы. Общие положения.
Композиции автоматов.
Моделью абстрактного автомата явля- ется объект с 1 входом и 1 выходом.
Ни вид сигналов, ни внутренняя струк- тура абстрактного автомата не рассмат- риваются.
В структурной теории автоматов обьек- том изучения являются так называемые структурные автоматы и их композиции.
Структурный автомат - это объект, име- ющий совокупность входных и выход- ных каналов (входов и выходов), по ко- торым передаются элементарные сигна- лы, представляющие перерабатываемые автоматом символы.
Наборы символов структурного алфа- вита однозначно задают (кодируют) символы алфавитов абстрактного автомата. Кодируя символы абстрактного автома- та, можно перейти от описания поведе- ния абстрактного автомата к описанию структурного. (Возможен и обратный переход.)
В примере структурный алфавит для всех символов двоичный:
x0 = (0;1) , x1 = (0;1) y0 = (0;1) , y1 = (0;1)
Композиция структурных автоматов состоит в том, что для совокупности автоматов производится отождествле- ние (соединение) входов и выходов отдельных автоматов. Некоторые вхо- ды и выходы при этом отмечаются как внешние.
Автоматы, образующие композицию, работают в некоторой системе тактнос- ти. Выделение тактов и пауз между ними
Период такта - время от начала i-го до начала (i+1) -го такта (i-ый период).
В структурной теории авиоматов поня- тие такта детализируется, т.к. в ней, в частности, рассматривается задача пос- троения физических моделей автоматов и способы интерпретации систем тактности.
Для автомата существует интервал времени в периоде t, когда значения X неизменны и в соответствии с функциями выходов и переходов оп- ределяют значения Y и S. Это время будем называть входным микротактом t1.
Интервал времени в периоде t, когда значения Y неизменны и соответствуют значениям функции выходов, будем на- зывать выходным микротактом t0.
В композиции автоматов соединение выхода автомата Ai со входом автомата Aj возможно только в случае, если со- вместим с , то-есть, если любой момент времени из принадлежит .
Наиболее употребимы следующие варианты организации тактности:
1.Композиции автоматов с единой (общей для всех автоматов) системой такт-ности.
Для такой композиции существует единое (общее) разбиение полуоси времени на периоды тактов для всех автоматов композиции.
2. Композиции автоматов с различными системами тактов.
В таких композициях автоматы могут быть разбиты на под- множества авто матов, в каждом из которых использу ется своя единая система тактности.
При этом можно выделить два основ- ных вида композиций:
а) композиции с несопрягаемыми системами тактов;
б) композиции с сопрягаемыми системами тактов;
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (552)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |