Общие теоретические положения
Эксперименты с автоматами. Синтез автоматов по дереву управления
Существуют ситуации, когда не дано общее описание поведения проектируемого автомата, но известно, во что автомат перерабатывает входные слова.
Данную ситуацию можно характеризовать следующим образом. Пусть задан автомат, называемый "черный ящик", о внутренней структуре которого ничего или почти ничего не известно. На вход автомата можно подавать входные слова и наблюдать соответствующие выходные слова. Требуется расшифровать его, т.е. построить абстрактный автомат, работающий так же, как и "черный ящик".
Такой подход называется экспериментальным.
Эксперименты могут быть кратные и простые, оба в свою очередь могут быть условными и безусловными.
Для кратных экспериментов характерным является наличие кнопки возврата в начальное состояние. Перед очередным вопросом автомат переводится в начальное состояние.
При простых экспериментах кнопка возврата отсутствует. Каждый следующий вопрос задается "черному ящику" в том состоянии, в котором он оказался в результате ответа на предыдущий вопрос.
В Условных экспериментах очередной вопрос зависит от ранее заданных вопросов.
В безусловных экспериментах каждый очередной вопрос не зависит от ранее заданных вопросов и ответов. Все вопросы уже заранее фиксированы.
При безусловных экспериментах осуществляется полный перебор всех допустимых слов одной установленной длины. Число экспериментов в этом случае определяется как 
.
|
|
|
В условных экспериментах используется априорная информация: r - степень различимости автомата.
Алгоритм организации условного эксперимента.
1. Построить дерево высотой h0=r+1
2. Выделить базис для k-го яруса (k=1, 2, 3 …)
3. Продолжить эксперимент на 1 букву, т.е. перейти на следующий ярус только относительно вершин найденного базиса.
4. Перейти к п.2. и продолжить выделять базис для k=k+1 до «насыщения», т.е. до тех пор, пока будут появляться новые неразличимые вершины. Как только будет получено, что все новые вершины являются неразличимыми с ранее поименованными, будет достигнуто состояние «насыщения».
Результаты эксперимента удобно представлять в виде дерева, которое называется деревом управления. Корнем дерева управления является начальное состояние.
Высота дерева h определяется количеством ярусов и соответствует длине входных/выходных слов.
Вершины 1-го яруса отображают реакции автомата на все слова длины 2 и т.д.
Каждый путь в дереве определяет входное слово.
При построении дерева (в поведенческой теории) следует придерживаться соглашений:
|
|
|
На дереве управления входные буквы не пишутся, а подразумевается, что они следуют в заранее определенном порядке; на ребрах дерева запись производится только выходных букв.
Вершины дерева нумеруются по мере перехода на старшие яруса слева-направо.
Для записи порядка следования входных букв используют схему, называемую ключом дерева. Например, задан входной алфавит X={0, 1}, тогда ключ будет выглядеть следующим образом: по левой ветви будет выполняться переход на следующий ярус, если на вход поступает 0, а по левой ветви – если на вход поступает 1. Можно и наоборот – все зависит от поставленной задачи и желания исследователя.
Переход от дерева управления к представлению автомата в виде графа с меньшим числом состояний называют сверткой дерева управления. Свертка состоит из 2-х этапов: 1) Выделение базиса; 2) Построение граф-схемы переходов.
Правила Выделения базиса.
1. Вершины дерева именуются по мере перехода на старшие яруса и внутри слева-направо.
2. Вершины неразличимые с уже поименованными вершинами именуются аналогично. Если вершина неразличима с несколькими вершинами, то она именуется списком имен этих вершин.
3. Базис составляют вершины, в которые существует путь из начальной вершины (корня). Имена вершин, составляющих базис должны быть различны. Т.О. вершины с повторяющимися именами на более верхних ярусах исключаются из рассмотрения.
Дата добавления: 2019-02-22; просмотров: 286; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!