Абстрактный синтез конечных автоматов.

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

Исходные данные задаются в виде алфавитного оператора. Алфавитный оператор называется оператор, устанавливающий соответствия между входными и выходными словами, которые перерабатывает автомат.

t₀ t₁ t₂ t₃

P₀ P₁ P₂ P₃

Индексы указывают на номера машинного такта, а не на различие между буквами.

P = {0 , 1}

W = {0 , 1}

P₀ P₁ P₂ P₃ W₀ W₁ W₂ W₃

0 0 0 0 0 0 0 0

0 0 0 1 0 0 1 0

0 1 0 0 0 1 0 0

1 0 0 0 1 0 0 0

Алфавит операций называется автоматным, если он удовлетворяет следующим условиям:

1. Однозначно отображает входные слова в выходные

2. Удовлетворяет условию полноты, т.е. представляет все входные последовательности входящие в допустимый набор P_g^*

3. Оператор сохраняет длину преобразованного слова

4. Оператор осуществляет преобразование одинаково локальных отрезков входного слова в совпадающие начальные отрезки выходных слов.

Утверждение :

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

Для полученного автоматного алфавитного оператора из не автоматного используют 2 операции : выравнивание и пополнение. Операция выравнивания используется, если нарушено условие автоматности оператора и заключается в добавлении нового пустого символа eсправа во всех последующих или слева к выходной.

Явно восстанавливаем 3 условие автоматности оператора.

Пример :

Нарушено 3 условие – длина выходного слова меньше длины входного, поэтому слева к выходному слову добавляют пустой символ e.

После пополнения выходной алфавит будет выглядеть: W= {0 , 1 ,e}

P= {0 , 1}

W= {0 , 1} – изначально

Операция пополнения используется если нарушено 4 условие и заключается в добавлении пустого символа eсправа к входной последовательности и слева к выходной одновременно.

Вначале P = {0 , 1}

W = {0 , 1}

Стало P = {0 , 1 , e}

W = {0 , 1 , e}

Начальный отрезок из одной буквы 0 в исходном операторе в первой строке преобразовывается в 0 а во втором в 1, следовательно нарушено 4 условие, поэтому к входному слову слева и к выходному слева дописывается пустой символ e, при этом изменяется входной и выходной алфавиты.

А операторы могут быть заданы двумя способами: табличным и графическим.

Пример :

P₀ P₁ P₂ W₀ W₁ W₂

0 0 e₁ e₁ 0 0

0 0 e₂ e 0 1

Если в операции пополнения используют несколько пустых символов e(e₁ ,e₂ , …), то можно восстановить первое условие автоматности.

P₀ P₁ W₀ W₁

0 0 0 0

0 0 0 1

Табличный способ устанавливает соответствие между входными и выходными последовательностями в форме таблицы.

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

Пусть от вершины к листу дерева соответствует одному входному слову.

Входные буквы помечают дуги между вершинами дерева. Выходное слово также присутствует на пути из корня к листу. Число ярусов дерева соответствует длине входного слова.