Реализация произвольного автомата в виде СЛС

Алгоритм построения СЛС
1. Двоичное кодирование алфавитов X, Y, Q (возможно, появятся резервные состояния).
2. Доопределение АТ на все состояния, в том числе и резервные. Цель: получить канонические уравнения наименьшей сложности.
3. Построение СЛС.

К примеру из лекции 1
⇒

Решение: ДМ
0/0
0/0
1/1
1/1
1/1
0/1
1/1
0/0
1/1
1/1
0/1
1/1
0/0
q0
q1
q2
q3
q6
q5
q4

АТ

1
1
1

1
1

СЛС к примеру
Сложность схемы = 28

0/0
0/0
1/1
1/1
1/1
0/1
1/1
0/0
1/1
1/1
0/1
1/1
0/0
q2
q3
q6
q5
q1
q4
ДМ с ветвями резервных состояний
q0
q7
1/1
0/1

Доказательство теоремы о реализации произвольного автомата в виде СЛС

§2. Автоматное отображение

§3. Эквивалентные состояния и эквивалентные автоматы.

Пример:
1/0
0/0
0/0
1/1
1/1
0/1
0
0
0
0
1
1
1
1
S
T
1/0
1/1
S~
T
0/0
0/1

§4. Теорема о существовании минимального автомата
x
x

Схема доказательства

§5. Алгоритм минимизации автомата.
(алгоритм Ауфенкампа и Хона)

Пример:
1.
2.

3.
4.

5.
Smin

Обоснование алгоритма

Тогда
И т.д., пока не дойдем до классов первого порядка