1. Определение в таблице одинаковых переходов/выходов и пометка их .

	S0	S1	S2	S3
X1	S1 Y1	S0 Y2	S1 Y1	S0 Y1
	q3	q2	q3	q1
X2	S2 Y2	S2 Y2	S3 Y1	S1 Y2
	q5	q5	q6	q4

Пометка начинается с анализа состояния S₀ и выходной реакции Y₁ . Если такая комбинация S₀/Y₁ встречается в таблице, то ей приписывается пометка q₁ Если рассматриваемая комбинация встречается несколько раз, то всем приписывается одинаковая пометка. Далее анализируется наличие комбинации S₀/Y₂ , если она встречается, то ей приписывается пометка q₂ , и так далее рассматривается наличие всех комбинаций <состояние>/<буква вых. алфавита> и всем приписываются пометки.

2. Запись множеств эквивалентных состояний

Каждому исходному состоянию приписывается множество соответствующих им пометок (рассматривается построенная таблица с пометками). Ищется в таблице очередное исходное состояние и в соответствующее множество записывается приписанная ему пометка. Для начального состояния S₀ в множество пометок добавляется также q₀ - для идентификации начального состояния автомата Мура.

Для рассматриваемого примера получены следующие множества эквивалентных состояний .

3. Построение отмеченной таблицы переходов автомата Мура в соответствии с п.1 и 2.

	-	Y2	Y1	Y1	Y2	Y2	Y1
	q0	q1	q2	q3	q4	q5	q6
X1	q3	q3	q3	q2	q2	q3	q1
X2	q5	q5	q5	q5	q5	q6	q4

Общее количество состояний искомого эквивалентного автомата Мура = суммарному количеству проставленных пометок + метка начального состояния q₀, т.е. сумме количества элементов всех построенных эквивалентных множеств. В данном случае множество состояний автомата Мура будет следующим: .

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

Запись переходов: рассматриваются множества эквивалентных состояний и в столбцы таблицы автомата Мура, соответствующие элементам рассматриваемого множества, записываются проставленные пометки из столбца соответствующего эквивалентного состояния автомата Мили, например, в столбцы состояний q₀ q₁ q₂ автомата Мура будут записаны пометки q₃ q₅ из столбца S₀ таблицы автомата Мили.

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

Билет №21. Абстрактный синтез автоматов по регулярным выражениям Первичное описание автомата x={x1,x2,..,xm} y={y1,y2,…,yn} n и m – не обязательно равны. Rj –событие, множество возможных слов из алфавита Х, вызывающее появление на выходе автомата определенной буквы yi. Пример. Построить автомат для выдачи магнитной карты в метро. Автомат принимает монеты достоинством 1 или 2 руб., карта стоит 4руб.

Решение: Входной алфавит X={1, 2} – в соответствии с монетами, которые может принимать автомат. Выходной алфавит – 1- выдача карты, 0 – отказ/ожидание, с – сброс/возврат денег, Y={1, 0, c}. РВ, соответствующее выдаче карты – перебор комбинаций монет 1 и 2, чтобы получить требуемую сумму 4руб. в т.ч. без сдачи - РВ, описывающее сброс монет при неверной сумме – РВ при отказе – Язык регулярных выражений основывается на алгебре событий. Алгебра событий в алфавите Х называется множество всех событий в этом алфавите, на котором определены 3 операции: 1) Дизъюнкция событий R1 R2 называется событие R, представляющее собой объединение R1 R2. 2)Конъюкцией событий R1 R2 называется событие R, полученное путем приписывания каждому слову события R1 последовательно каждое слово события R2. 3) Итерацией некоторого слова р называется дизъюнкция пустого слова, слова р, слова рр, слова ррр и т.д. Определение. Любое событие, которое можно получить из букв заданного алфавита с помощью конечного числа операций называется регулярным событием, а выражение, составленное с помощью этих операций с указанием выходной реакции называется регулярным выражением. Приоритеты выполнения операций 1. 2. 3. Теорема Клини. Регулярные события, и только они, представлены в конечных автоматах. (Язык регулярных выражений достаточен для описания любого, сколь угодно сложного конечного автомата) Тождественные преобразования в алгебре регулярных событий аналогичны 7 свойствам алгебры-логики. По регулярным выражением возможно построение графов. - Все пути в графе должны соответствовать последовательности входных букв, которые принадлежат данному РВ и наоборот. - При построении графа РВ возможны случаи образования ложных путей, которые соответствуют, не принадлежащим регулярным выражениям. Для избежания образования ложных путей используют пустые стрелки. Пустая стрелка представляет мгновенный переход из исходной вершины в конечную. Номер вершины откуда выходит пустая стрелка приписывается слева от номера вершины в которую входит пустая стрелка. Правило Кузнецова. Пустые стрелки ставятся в случаях: - Произведение двух или более итераций - Если хотя бы один из термов начинается с итерационной скобки (Пустая стрелка определяет начало терма) -При умножении на дизъюнкцию, если хотя бы один терм заканчивается конъюкцией - При вложенных итерациях Правила синтеза КА по РВ: 1) Преобразование регулярных выражений 2) Построение графа по регулярным выражениям по правилам Кузнецова 3) Графы объединяют по первой вершине 4) Перенумерация вершин 5) Вершинам объединенного графа приписываются выходные буквы 6) Построение таблицы переходов автомата Мура. 7) Выделяется первый столбец (помеченный цифрой 1) 8) Состояния формируются как дизъюнкция вершин объединенного графа регулярных выражений 9) Столбцы помещаются дизъюнкцией номеров вершин 10) Из вершины 1 рассматриваются все исходящие дуги, помеченные одной и той же входной буквой. Эти вершины образуют дизъюнкцию 11) Полученными дизъюнкциями помечаются столбцы 12) Если вершина обозначается несколькими номерами, то в дизъюнкцию записывается крайний правый. 13) Столбцы помечаются буквами выходного алфавита.

Билет №22. Эксперименты над автоматами: типизация, основные понятия. Существуют ситуации, когда не дано общее описание поведения проектируемого автомата, но известно, во что автомат перерабатывает входные слова. Данную ситуацию можно характеризовать следующим образом. Пусть задан автомат, называемый "черный ящик", о внутренней структуре которого ничего или почти ничего не известно. На вход автомата можно подавать входные слова и наблюдать соответствующие выходные слова. Требуется расшифровать его, т.е. построить абстрактный автомат, работающий так же, как и "черный ящик".

Такой подход называется экспериментальным.

Эксперименты могут быть кратные и простые, оба в свою очередь могут быть условными и безусловными.

Для кратных экспериментов характерным является наличие кнопки возврата в начальное состояние. Перед очередным вопросом автомат переводится в начальное состояние.

При простых экспериментах кнопка возврата отсутствует. Каждый следующий вопрос задается "черному ящику" в том состоянии, в котором он оказался в результате ответа на предыдущий вопрос.

В Условных экспериментах очередной вопрос зависит от ранее заданных вопросов.

В безусловных экспериментах каждый очередной вопрос не зависит от ранее заданных вопросов и ответов. Все вопросы уже заранее фиксированы.

При безусловных экспериментах осуществляется полный перебор всех допустимых слов одной установленной длины. Число экспериментов в этом случае определяется как .

В условных экспериментах используется априорная информация: r - степень различимости автомата.

Алгоритм организации условного эксперимента.

1. Построить дерево высотой h₀=r+1

2. Выделить базис для k-го яруса (k=1, 2, 3 …)

3. Продолжить эксперимент на 1 букву, т.е. перейти на следующий ярус только относительно вершин найденного базиса.

4. Перейти к п.2. и продолжить выделять базис для k=k+1 до «насыщения», т.е. до тех пор, пока будут появляться новые неразличимые вершины. Как только будет получено, что все новые вершины являются неразличимыми с ранее поименованными, будет достигнуто состояние «насыщения».

Билет №23. Поведенческий подход к синтезу автоматов. Абстрактный синтез по дереву управления. Результаты эксперимента удобно представлять в виде дерева, которое называется деревом управления. Корнем дерева управления является начальное состояние.

Высота дерева h определяется количеством ярусов и соответствует длине входных/выходных слов. Вершины 1-го яруса отображают реакции автомата на все слова длины 2 и т.д. Каждый путь в дереве определяет входное слово. При построении дерева (в поведенческой теории) следует придерживаться соглашений: На дереве управления входные буквы не пишутся, а подразумевается, что они следуют в заранее определенном порядке; на ребрах дерева запись производится только выходных букв. Вершины дерева нумеруются по мере перехода на старшие яруса слева-направо. Для записи порядка следования входных букв используют схему, называемую ключом дерева. Например, задан входной алфавит X={0, 1}, тогда ключ будет выглядеть следующим образом: по левой ветви будет выполняться переход на следующий ярус, если на вход поступает 0, а по левой ветви – если на вход поступает 1. Можно и наоборот – все зависит от поставленной задачи и желания исследователя.

Переход от дерева управления к представлению автомата в виде графа с меньшим числом состояний называют сверткой дерева управления. Свертка состоит из 2-х этапов: 1) Выделение базиса; 2) Построение граф-схемы переходов. Правила Выделения базиса.

1. Вершины дерева именуются по мере перехода на старшие яруса и внутри слева-направо.

2. Вершины неразличимые с уже поименованными вершинами именуются аналогично. Если вершина неразличима с несколькими вершинами, то она именуется списком имен этих вершин.

3. Базис составляют вершины, в которые существует путь из начальной вершины (корня). Имена вершин, составляющих базис должны быть различны. Т.О. вершины с повторяющимися именами на более верхних ярусах исключаются из рассмотрения.