2.1.2. Приведенная форма автомата
Вернемся к задаче минимизации полного автомата. Из определения неотличимых состояний следует, что поведение автомата в этих состояниях для любой входной последовательности одинаково. Поэтому для минимизации полного автомата достаточно объединить в одно состояние все неотличимые состояния.
Поставим формально задачу минимизации полного автомата. Рассмотрим два автомата с одинаковыми входным и выходным алфавитами и .
Определение. Автоматы и эквивалентны, если для любого состояния автомата найдется неотличимое состояние автомата , и наоборот, для любого состояния автомата найдется неотличимое состояние автомата .
Задачу минимизации полного автомата можно сформулировать так: построить автомат, эквивалентный данному, с минимальным числом состояний.
Определение. Автомат называется приведенным, если любые два состояния в нем отличимы.
Определение. Приведенный автомат,
эквивалентный заданному автомату
,
называется приведенной формой
автомата
и обозначается
.
Теорема. Приведенная форма автомата есть автомат с минимальным числом состояний, эквивалентный автомату .
Доказательство. Рассмотрим автомат
,
его приведенную форму
,
и произвольный автомат
,
эквивалентный автомату
.
Поскольку отношение неотличимости
является транзитивным, нетрудно показать,
что автоматы
и
также эквивалентны, т.е. для каждого
состояния автомата
найдется неотличимое состояние автомата
.
Рассмотрим два различных состояния
,
для них в автомате
найдутся состояния
. Поскольку все состояния автомата
отличимы, то
.
Следовательно, число состояний в автомате
не меньше числа состояний в автомате
.
■
Итак, минимизировать полный автомат – это значит найти его приведенную форму. Рассмотрим процесс ее построения.
Отношение неотличимости на множестве
,
как нетрудно убедиться, является
отношением эквивалентности, и,
следовательно, разбивает
на классы эквивалентности, называемые
классами неотличимости. Пусть
– разбиение
на классы неотличимости. Построим
автомат
,
где
;
;
.
Определение является корректным, так
как столбцы таблицы выходов неотличимых
состояний одинаковы, а столбцы таблицы
переходов отличаются только символами
неотличимых состояний, то есть все
состояния из одного класса неотличимости
по одному и тому же входному символу
переходят в один класс. Из определения
автомата
видно, что любые его два состояния
отличимы, поскольку неотличимые состояния
принадлежат одному из классов
неотличимости. Автоматы
и
эквивалентны, так как состояние
неотличимо от состояния
,
такого, что
,
и наоборот,
неотличимо от любого состояния
,
такого, что
.
Окончательно получаем, что автомат
есть приведенная форма автомата
.
Пример. Рассмотрим автомат из предыдущего примера, для него найдены пары неотличимых состояний:
.
Отсюда разбиение на классы неотличимости имеет вид:
.
Сгруппируем состояния в таблицах переходов и выходов по классам, получим
|
|
|
|
y |
|
|
|
|
X\Q |
1 |
3 |
2 |
4 |
5 |
6 |
7 |
8 |
|
7 |
8 |
7 |
8 |
7 |
5 |
1 |
3 |
|
6 |
6 |
2 |
2 |
4 |
1 |
8 |
8 |
|
1 |
3 |
1 |
3 |
3 |
1 |
3 |
1 |
|
|
|
|
j |
|
|
|
|
X\Q |
1 |
3 |
2 |
4 |
5 |
6 |
7 |
8 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Построим автомат по определению. Объединим столбцы состояний из одного класса неотличимости в один столбец, заменив номера состояний обозначениями классов неотличимости.
|
|
|
|
|
|
|
|
|
|
|
X\Q |
|
|
|
|
|
X\Q |
|
|
|
|
|
|
|
|
|
|
a |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
b |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
c |
0 |
0 |
0 |
0 |
Этот автомат является приведенной формой исходного автомата.
Таким образом, для минимизации автомата необходимо построение классов неотличимости. Поиск их с помощью графа условий неотличимости может оказаться достаточно громоздким, поэтому рассмотрим другие алгоритмы.