Лекции Русакова (1021002), страница 16
Текст из файла (страница 16)
Любое слово pвходного алфавита на котором отображение ϕ определено, имеет ту жедлину, что и его образ ϕ (p). В частности, пустое слово переводитсяотображением ϕ в пустое слово.4. Автоматное отображение ϕ переводит любой начальный отрезокслова р, на котором оно определено, в соответствующий (имеющий ту жедлину) начальный отрезок слова ϕ (p).149Определение.Перечисленные условия (1-4) называются условиями автоматностиотображения.Все слова входного алфавита разбиваются автоматным отображениемна два класса: на класс допустимых и класс запрещенных слов.Определение.Совокупность всех запрещенных слов для данного автоматногоотображения будет называться его областью запрета.Рассмотрим произвольное (частичное) отображение ϕ , для котороговыполняются сформулированные выше условия.
Построим абстрактный(частичный) автомат Мура U, состояниями которого будут служитьвсевозможные допустимые для отображения ϕ слова входного алфавитаХ=(х1,…, хn).Обозначим множество всех таких слов через А и определим функциюпереходов δ(а,x) этого автомата следующим образом: если аj – любое словоиз А, а xi – произвольная буква входного алфавита, то будем считать, чтоδ(аj,xi) равняется слову аjxi (получающемуся в результате приписываниябуквы xi к слову аj), если слово аjxi содержится в А, и что δ(аj,xi) неопределена в противном случае.Выбирая в качестве выходного алфавита автомата U выходной алфавитотображения φ, построим сдвинутую функцию выходов λ(а) автоматаМура U следующим образом: для любого непустого слова аi из А полагаемλ(аi) равным последней букве слова φ(аi); на пустом слове функция λ(a)остается неопределенной.150В качестве начального состояния автомата выбираем пустое слово ε иполучаем автомат Мура, индуцирующий исходное отображение φ.
В самомделе, пусть, q=xi1,xi2,…,xik – любое допустимое слово отображения φ. Тогдавсе его начальные отрезки будут также допустимыми словами (в силуусловия 2). После подачи на вход построенного автомата слова q, будетосуществляться последовательный его перевод в состояние ε xi1=xi1,xi2,…, xik.При этом автомат выдает некоторую последовательность выходныхбукв yj1,yj2,…,yjk=p. Из способа определения данного автомата следует, чтопоследняя буква слова р совпадает с последней буквой слова φ(q),предпоследняя буква слова р – с последней буквой слова φ(xi1,xi2,…,xik-1),которая в силу условия 4, совпадает с предпоследней буквой слова φ(q) и т. д.Продолжая сравнение и используя условия 3, можно установить совпадениевсех букв слова р с соответствующими им буквами слова φ(q).Следовательно, построенный автомат Мура U индуцирует исходное(частичное) отображение φ.
Поскольку можно интерпретировать автоматМура U как автомат Мили, то очевидно следующее предложение.Определение.Еслиалфавитноеотображениеφудовлетворяетусловиямавтоматности, то можно построить автоматы Мили и Мура (как правило,бесконечные), индуцирующие это отображение.В случае, когда область определения отображение φ конечна, этиавтоматы также можно считать конечными.Данное предложение позволяет применять термины «автоматноеотображение» по всему алфавитному отображению, удовлетворяющемуусловиям автоматности. Из этого предложения вытекает конструктивныйприем, позволяющий по любому автоматному отображению с конечной151областью определения (заданному на конечном множестве слов) строитьиндуцирующий это отображение конечный автомат Мили или Мура.Ранее рассматривалась возможность интерпретации автомата Мура какавтомат Мили с тем же самым числом состояний.Теорема.Для всякого конечного автомата Мили существует эквивалентный ему(индуцирующий то же самое отображение) конечный автомат Мура.Существует единый конструктивный прием (универсальный алгоритмпреобразования автоматов Мили в автоматы Мура), позволяющий попроизвольному конечному автомату Мили, имеющему m входных сигналов иn состояний, построить эквивалентный ему автомат Мура, имеющий не болееm⋅n + 1 состояний.Условия автоматности накладывают весьма жесткие ограничения накласс отображений, которые могут быть индуцированы абстрактнымиавтоматами.
Большинство алфавитных отображений, с которыми приходитсяиметь дело на практике, в частности большинство алгоритмов, неудовлетворяют этим условиям.Существует, однако, стандартный прием, позволяющий индуцироватьлюбое алфавитное отображение в автоматное.Рассмотрим этот прием.Пусть φ – произвольное (как правило, частичное) отображениемножества слов в (конечном) алфавите Х в множество слов в (конечном)152алфавите Y. Обозначим через Р область определения этого отображения.Будем применять к отображению φ две операции.Первая операция – выравнивания длин слов (операция выравнивания).Её суть: во входной и выходной алфавиты отображения φ (т.
е. Х и Y)добавляется по одной новой букве, которые будем называть пустыми иобозначать через α и β.Каждому слову р из Р приписывается справа mp экземпляров букв α, ак его образу q = φ(p) приписывается слева nq экземпляров букв β так, чтобыдлины полученных в результате приписывания новых букв словам р1 и q1совпали.Далее строится новое отображение φ1 некоторого множества Р1, слов валфавите Х U(α) в множества слов в алфавите Y U (β), которое переводитдруг в друга слова р1 и q1, полученные в результате выравнивания длин словр и q соответственно: φ1(р1)= q1 (р – пробегает при этом все множество P).Условимся считать, что отображение φ1, получается из отображения φс помощью операции выравнивания. Существует некоторая стандартнаяоперациявыравнивания,прикоторойотображениеφ1 ,однозначноопределяется отображением φ и присоединенными пустыми буквами α и β.Суть ее в том, что число mp пустых букв α, приписываемых справа кпроизвольному слову р из области определения отображения φ, принимаетсяравным длине слова q = φ(p), а число nq пустых букв β, приписываемых слевак слову q, принимается равным длине слова р.Вторая операция применяется только к выравниванию алфавитныхотображений φ, т.
е. к таким отображениям у которых длины входных исоответствующих им выходных слов равны между собой. Сущность этойоперации –операции пополнения отображения φ, заключается враспространении отображения φ на начальные отрезки слов.153Если s – произвольный начальный отрезок любого слова р из областиопределения отображения φ, то полагаем φ(s) равным начальному отрезкуслова φ(p), т. е. имеющему длину s.В результате применения операции пополнения к произвольномувыровненному алфавитному отображению φ возникает новое отображение φ1область определения которого удовлетворяет условию полноты.
Условимсяназывать это отображение пополнением отображения φ.Если пополнение φ1 отображения φ является однозначным, тоочевидно, что оно удовлетворяет всем четырем условиям автоматности.4.13. Представление событий в автоматах.Основнойзадачейабстрактнойтеорииавтоматовявляетсяустановление связей, существующих между автоматами и индуцируемымиими отображениями.Определение.Произвольное автоматное отображение можно задавать событиями,которые соответствуют этим отображениям.Определение.Для произвольного автомата А множество Sy всех входных слов,вызывающих появление выходных слов, которые оканчиваются одной и тойже буквой (выходным сигналом) у, называется событием, представленным вавтомате А выходным сигналом у. Множество, состоящее из событий Sу, длявсех букв выходного алфавита автомата А, называется каноническиммножеством событий данного автомата А.154Определение.Каноническоемножествособытийлюбогоавтоматаявляетсяавтоматным множеством событий.Очевидно и обратное, что для любого автоматного множества событийM существует такой автомат (в качестве которого можно выбрать какавтомат Мили, так и автомат Мура), каноническое множество событийкоторого совпадает с множеством M.Определение.В отличие от автоматного отображения абстрактный автомат неопределяется однозначно соответствующим ему каноническим множествомсобытий, поскольку одно и то же автоматное отображение можетиндуцироваться различными автоматами.Важные задачи абстрактной теории автоматов:1.
ЗадачанахождениясоответствующегоемупозаданномуканоническогоабстрактномуавтоматуАмножествасобытий–каноническая задача анализа абстрактного автомата;2. Обратная задача, по заданному автоматному множеству событий Mнаходить абстрактный автомат, каноническое множество событий котороесовпадает с M – каноническая задача синтеза абстрактного автомата.4.14. Регулярные языки и конечные автоматы.Определение.Любое автоматное отображение φ может быть задано конечныммножеством М событий во входном алфавите этого отображения.155Если область определения отображения φ конечна, то все событиямножества М конечны. Конечное событие можно задать, перечислив все егоэлементы.
Ясно, что в случае, когда область определения отображения φбесконечна, хотя бы одно из событий множества М также будетбесконечным. Поэтому необходимо разработать специальный язык, которыйпозволялбыпредставлять(описывать)бесконечныесобытия,соответствующими конечными выражениями.Для языка регулярных выражений алгебры событий используются триоперации над событиями:1) А∪В – объединение (дизъюнкция);2) А⋅В – умножение (конкатенация);3) {A} – итерация (обозначается также А*).Определим конечные множества входных букв Х = {x1, ..., xn} изададим для этого множества регулярное выражение.Определение.Регулярным выражением в алфавите Х называется выражение,построенное из букв алфавита Х и из символов операций объединения,умножения и итерации с использованием соответствующим образом круглыхскобок.Всякое регулярное выражение определяет некоторое событие S(событие S получается в результате выполнения всех операций, входящих врегулярное выражение).
События, определяемые таким образом, называютсярегулярными событиями над алфавитом Х. Другими словами регулярным156событием (или языком) называется событие, полученное из элементарныхсобытий (однобуквенных слов xi) применением конечного числа разопераций дизъюнкции, конкатенации и итерации.Например, в алфавите из трех букв x, y, z регулярное выражениеx {x ∨ y ∨ z} (y ∨ z) задает регулярное событие, состоящее из всехслов, которые начинаются буквой х и заканчиваются буквой y или z. Дляконечных автоматов характерны только регулярные события.Определение.Общая задача анализа абстрактного автомата ставится как задачанахождения по заданному абстрактному автомату такого события, котороепредставлено любым множеством его состояний.Определение.Общая задача синтеза абстрактного автомата ставится как задачапостроения по любому конечному множеству событий такого автомата,который представляет каждое событие этого множества некоторыммножеством своих выходных сигналов4.15. Основнойалгоритмсинтезаконечныхавтоматов.Определение.Основной алгоритм синтеза конечных автоматов это алгоритм,который позволяет по любому конечному множеству М регулярных событий,заданных своими регулярными выражениями, находить таблицу переходов ивыходов конечного вполне определенного автомата Мили и отмеченную157таблицу переходов конечного вполне определенного автомата Мура.
Таких,что все события множества M представляются как в автомате Мили, так и вавтомате Мура некоторыми множествами их выходных сигналов.Перейдем от представления событий R1,...,Rp в автомате Мурамножествами состояний к представлению их множествами выходныхсигналов. Для этого достаточно в качестве выходных сигналов взятьразличные подмножества заданного множества событий (R1,…,Rp) иотмечать каждое состояние q автомата множеством тех событий, которыесодержат слова, переводящие автомат из начального состояния в состояние q.Если состояния, не представляют ни одного из заданных событий, тоони отмечаются пустым множеством событий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
