Определение.

Если алфавитное отображение φ удовлетворяет условиям автоматности, то можно построить автоматы Мили и Мура (как правило, бесконечные), индуцирующие это отображение.

В случае, когда область определения отображение φ конечна, эти автоматы также можно считать конечными.

Данное предложение позволяет применять термины «автоматное отображение» по всему алфавитному отображению, удовлетворяющему условиям автоматности. Из этого предложения вытекает конструктивный прием, позволяющий по любому автоматному отображению с конечной областью определения (заданному на конечном множестве слов) строить индуцирующий это отображение конечный автомат Мили или Мура.

Ранее рассматривалась возможность интерпретации автомата Мура как автомат Мили с тем же самым числом состояний.

Теорема.

Для всякого конечного автомата Мили существует эквивалентный ему (индуцирующий то же самое отображение) конечный автомат Мура.

Существует единый конструктивный прием (универсальный алгоритм преобразования автоматов Мили в автоматы Мура), позволяющий по произвольному конечному автомату Мили, имеющему m входных сигналов и n состояний, построить эквивалентный ему автомат Мура, имеющий не более m⋅n + 1 состояний.

Условия автоматности накладывают весьма жесткие ограничения на класс отображений, которые могут быть индуцированы абстрактными автоматами. Большинство алфавитных отображений, с которыми приходится иметь дело на практике, в частности большинство алгоритмов, не удовлетворяют этим условиям.

Существует, однако, стандартный прием, позволяющий индуцировать любое алфавитное отображение в автоматное.

Рассмотрим этот прием.

Пусть φ – произвольное (как правило, частичное) отображение множества слов в (конечном) алфавите Х в множество слов в (конечном) алфавите Y. Обозначим через Р область определения этого отображения. Будем применять к отображению φ две операции.

Первая операция – выравнивания длин слов (операция выравнивания).

Её суть: во входной и выходной алфавиты отображения φ (т. е. Х и Y) добавляется по одной новой букве, которые будем называть пустыми и обозначать через α и β.

Каждому слову р из Р приписывается справа mp экземпляров букв α, а к его образу q = φ(p) приписывается слева nq экземпляров букв β так, чтобы длины полученных в результате приписывания новых букв словам р₁ и q₁ совпали.

Далее строится новое отображение φ₁ некоторого множества Р₁, слов в алфавите Х U(α) в множества слов в алфавите Y U (β), которое переводит друг в друга слова р₁ и q₁, полученные в результате выравнивания длин слов р и q соответственно: φ₁(р₁)= q₁ (р – пробегает при этом все множество P). Условимся считать, что отображение φ₁, получается из отображения φ с помощью операции выравнивания. Существует некоторая стандартная операция выравнивания, при которой отображение φ₁, однозначно определяется отображением φ и присоединенными пустыми буквами α и β. Суть ее в том, что число mp пустых букв α, приписываемых справа к произвольному слову р из области определения отображения φ, принимается равным длине слова q = φ(p), а число nq пустых букв β, приписываемых слева к слову q, принимается равным длине слова р.

Вторая операция применяется только к выравниванию алфавитных отображений φ, т. е. к таким отображениям у которых длины входных и соответствующих им выходных слов равны между собой. Сущность этой операции – операции пополнения отображения φ, заключается в распространении отображения φ на начальные отрезки слов.

Если s – произвольный начальный отрезок любого слова р из области определения отображения φ, то полагаем φ(s) равным начальному отрезку слова φ(p), т. е. имеющему длину s.

В результате применения операции пополнения к произвольному выровненному алфавитному отображению φ возникает новое отображение φ₁ область определения которого удовлетворяет условию полноты. Условимся называть это отображение пополнением отображения φ.

Если пополнение φ₁ отображения φ является однозначным, то очевидно, что оно удовлетворяет всем четырем условиям автоматности.

13. Представление событий в автоматах.

Основной задачей абстрактной теории автоматов является установление связей, существующих между автоматами и индуцируемыми ими отображениями.

Определение.

Произвольное автоматное отображение можно задавать событиями, которые соответствуют этим отображениям.

Определение.

Для произвольного автомата А множество S_y всех входных слов, вызывающих появление выходных слов, которые оканчиваются одной и той же буквой (выходным сигналом) у, называется событием, представленным в автомате А выходным сигналом у. Множество, состоящее из событий S_у, для всех букв выходного алфавита автомата А, называется каноническим множеством событий данного автомата А.

Определение.

Каноническое множество событий любого автомата является автоматным множеством событий.

Очевидно и обратное, что для любого автоматного множества событий M существует такой автомат (в качестве которого можно выбрать как автомат Мили, так и автомат Мура), каноническое множество событий которого совпадает с множеством M.

Определение.

В отличие от автоматного отображения абстрактный автомат не определяется однозначно соответствующим ему каноническим множеством событий, поскольку одно и то же автоматное отображение может индуцироваться различными автоматами.

Важные задачи абстрактной теории автоматов:

1. Задача нахождения по заданному абстрактному автомату А соответствующего ему канонического множества событий – каноническая задача анализа абстрактного автомата;

2. Обратная задача, по заданному автоматному множеству событий M находить абстрактный автомат, каноническое множество событий которое совпадает с M – каноническая задача синтеза абстрактного автомата.