Правила построения граф-схемы переходов.
1. Любой вершине базиса ставится в соответствие состояние: 
.
2. Образование дуг графа
· если 
смежные, то из в направляется дуга, которой приписывается соответствующие входная и выходная буквы.
· если 
смежные, при чем вершина 
имеет обозначение 
, то дуга направляется из вершины 
в одну из вершин 
или 
.
Таким образом, процедура построения автомата по дереву управления неоднозначна. Но при этом все полученные автоматы являются эквивалентными.
Именование вершин дерева.
Корень дерева именуется сразу 
. Для остальных вершин именование выполняется следующим образом: для именования очередной вершины вырезается поддерево с корнем в этой вершине и последовательно совмещается с поддеревьями уже поименованных вершин. Если выходные реакции на ребрах сравниваемых поддеревьях совпадут, то неименованной вершине приписывается имя вершины, с поддеревом которой выходные реакции совпали. Эти вершины будут называться неразличимыми.
Пример1. Построить автомат, различающий четные и нечетные двоичные 4-х разрядные числа, поступающие на вход автомата старшими разрядами. Использовать безусловный кратный эксперимент.
Решение:
1. Определение входного и выходного алфавита
Входной алфавит основывается на двоичном алфавите, т.к. на вход поступают разряды двоичных чисел, следовательно, X={0, 1}.
Из условия задачи следует, что на выходе автомата должна появляться реакция о четности или нечетности поступившего 4-х разрядного числа, тогда выходной алфавит должен содержать Ч – четное число, Н – нечетное число.
|
|
|
Пока на вход автомата поступили не все разряды числа, автомат находится в состоянии ожидания, поэтому в этом случае его выходная реакция О – ожидание. Y={Ч, Н, О}.
2. Идея построения автомата
Цифры числа (разряды) поступают на вход автомата последовательно, следовательно и анализировать их надо последовательно. На вход могут поступить числа от 0000 до 1111. Пока на вод не поступит последний младший разряд – на выходе автомата реакция О (ожидание). После поступления последнего разряда если пришла 1, то реакция – Н (число нечетное), если поступил 0 – реакция Ч (число четное). Т.о. происходит полный перебор.
3. Дерево
Ключ дерева:
Базис B={V0, V1, V2, V3}
4. Граф
Вершинам базиса сопоставляются вершины графа автомата.
V0 ® S0 V1 ® S1 V2 ® S2 V3 ® S3
Пример 2. Построить автомат, определяющий все слова в алфавите A={a, b, ÿ- пробел}, длины которых больше двух букв. Использовать безусловный кратный эксперимент.
Примечание. 1) Пустое слово, т.е. ÿ считать ≤2; 2) Для определения длины слова на вход автомата подается только три первых символа.
|
|
|
Решение:
1. Определение входного и выходного алфавита
Входной алфавит соответствует алфавиту А из условия задачи, следовательно, X={ a, b, ÿ- пробел }.
Из условия задачи следует, что на выходе автомата должна появляться реакция о длине поступившего слова, тогда выходной алфавит должен содержать О- «ожидание», соответствует отсутствию окончательного ответа; ≤2 – слово меньше или равно двум символам; >2 – слово больше двух символов. Y={ О, ≤2, >2}.
2. Идея построения дерева.
На вход может поступить любая комбинация из символов входного алфавита, следовательно необходимо рассмотреть все возможные сочетания. Появление пробела свидетельствует о том, что слово закончилось, например, при поступлении комбинации abÿ - выходная реакция будет «≤2», длина слова составляет 2 символа, а пробел – признак конца слова.
3. Дерево
4. Граф автомата
Базис B={V0, V1, V2 }
Вершинам базиса сопоставляются вершины графа автомата.
V0 ® S0 V1 ® S1 V2 ® S2
Пример 3. Построить автомат, выполняющий функцию y=x/3. Числа x – двоичные 4-разрядные поступают на автомат младшими разрядами. XÎ{3, 6, 9, 12, 15}. При синтезе использовать условный эксперимент при r=2.
|
|
|
Решение:
1. Определение входного и выходного алфавита
Входной алфавит соответствует X={0, 1}.
Выходной алфавит соответствует Y={0, 1}, т.к. на выходе должен появляться результат деления на 3 входных двоичных 4-х разрядных чисел.
| x | x/3 | X Мл.р. ст.р. | Y=X/3 | |
| 0011 | 0001 | 1100 | 1000 | |
| 0110 | 0010 | 0110 | 0100 | |
| 1001 | 0011 | 1001 | 1100 | |
| 1100 | 0100 | 0011 | 0010 | |
| 1111 | 0101 | 1111 | 1010 |
h0=r+1, h0=3
2. Дерево
Ключ дерева:
Базис B={V0, V1, V2 }
3. Граф
Дата добавления: 2019-02-22; просмотров: 386; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!