Построение дерева входных последовательностей.

Пусть задан входной алфавит :

1. Фиксирована вершина, которая называется корнем дерева

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

3. Строится nвершин

4. Из каждой вершины проводят nдуг и так далее

5. Последняя вершина – лист– называется конечной вершиной.

На дереве каждому символу Pсоответствует свой символW_i

Чтобы построить автомат нужно : для полученного автомата по автоматному алфавитному оператору необходимо выполнить следующие действия :

1. Представить алфавит операций или представить в виде дерева входных последовательностей.

2. Отметить все вершины дерева символами соответствия автомата, при этом корень пометить начальным состоянием, а все листья конечными.

3. Для полученного автомата Мура вершины отметить символами выходных букв

Для полученного автомата Мили отметить дуги символами выходных букв

4. Все конечные вершины объединяются в одну

5. Найти эквивалентное состояние и объединить их между собой.

Нестрогое определение автомата

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

P_k / W_k

S_i

P_i

P_k / W_k

S_j

P_j

S_l

S_j

S_l

P_i

P_j

P_k / W_k

6. Для получения автомата многократного действия совмещаются вершина конечная с начальной.

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

Пример:

P0	P1	P2	W0	W1	W2
0	0	0	0	0	1
0	0	1	0	0	0
0	1	0	0	0	1
0	1	1	0	0	0
1	0	0	0	0	1
1	0	1	0	0	0
1	1	0	0	0	1
1	1	1	0	0	0

1. Строим дерево

алфавит:

P = {0 , 1}

W = {0 , 1}

S = {S₀ , S₁ , S₂ , S₃ , S₄ , S₅ , S₆ , S_k }

3. Строим автомат Миля.

0/ 1

4. Объединяем S_k

5. S₃ = S₄ - эквивалентно

S₅ = S₆

S_3,4 = S_5,6

S₁ = S₂

6. Автомат многократного действия

Теcт:

t0	t1	t2		ti
S0	S1	S2	S0	Si
0	0	0		Pi
	0	0	1	Wi

Si / Pi	0	1
S0	S1/0	S1/0
S1	S2/0	S2/0
S2	S0/1	S0/0

Абстрактный этап синтеза конечного автомата состоит из следующих подъэтапов:

1. Преобразование алфавитного оператора к автоматному виду.

2. Построение абстрактного автомата по полученному автоматному алфавитному оператору.

3. Минимизация числа состояний абстрактного автомата.