2.1.3. Построение классов неотличимости: алгоритм Мура
Пусть задан автомат
и натуральное число
.
Определение. Состояния
и
k–неотличимы (обозначается
),
если
.
Иначе эти состояния называются
k–отличимыми (обозначается
).
Лемма.
Если и
,
то
.
Если и
,
то
.
Если и
,
то
.
Доказательство. Первые два утверждения
очевидны. Докажем третье утверждение.
Так как
,
то
.
Так как
,
то
.
Из всех таких слов выберем слово
минимальной длины и представим его в
виде конкатенации
,
где
.
Рассмотрим состояния
,
.
Убедимся, что эти состояния удовлетворяют
лемме. Из выбора
следует, что
,
,
откуда следует, что
,
а значит,
.
В том, что
,
убедимся методом от противного.
Предположим, что
,
тогда
.
Рассмотрим слово
.
Очевидно, что
.
Тогда
и
,
откуда
,
что противоречит выбору
,
как кратчайшего отличающего слова для
и
.
■
Отношение k–неотличимости является
отношением эквивалентности на множестве
,
а значит, порождает разбиение
множества
на классы k–неотличимости.
Свойства разбиения
Если и принадлежат одному и тому же классу разбиения и
,
то
и
принадлежат одному и тому же классу
разбиения
.
Если и принадлежат разным классам разбиения и
,
то
и
принадлежат разным классам разбиения
.
Если
,
то
есть собственное (не совпадающее с
)
подразбиение
.
Эти свойства означают, что всякое
есть подразбиение всякого
при
,
и, если
,
то
.
Исходя из этого, разбиение
строится следующим образом. Последовательно
строятся разбиения
.
Как только на очередном шаге
совпадет с
,
разбиение
найдено и совпадает с
.
Алгоритм Мура построения классов неотличимости
Начало. Задан автомат . Требуется найти разбиение множества на классы неотличимости.
Шаг 1. Построим разбиение
:
состояния
и
поместим в один класс разбиения
тогда и только тогда, когда столбцы
и
в таблице выходов одинаковы. Положим
.
Шаг 2. Построим разбиение
следующим образом: состояния
и
из одного класса разбиения
поместим в один класс разбиения
тогда и только тогда, когда для всех
состояния
и
принадлежат одному классу разбиения
.
Шаг 3. Если
,
положим
и вернемся на шаг 2.
Конец. Искомое разбиение
.
Пример. Рассмотрим автомат из предыдущего примера
|
|
|
|
y |
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
7 |
7 |
8 |
8 |
7 |
5 |
1 |
3 |
b |
6 |
2 |
6 |
2 |
4 |
1 |
8 |
8 |
c |
1 |
1 |
3 |
3 |
3 |
1 |
3 |
1 |
|
|
|
|
j |
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
b |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
c |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Шаг 1. Разбиение имеет вид
.
Шаг 2. Сгруппируем состояния в таблице переходов в классы, состояния из различных классов выделим разным шрифтом.
|
|
|
|
y |
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
7 |
7 |
8 |
8 |
7 |
5 |
1 |
3 |
|
6 |
2 |
6 |
2 |
4 |
1 |
8 |
8 |
|
1 |
1 |
3 |
3 |
3 |
1 |
3 |
1 |
Состояния
остаются в одном классе, а состояние 6
образует новый класс, поскольку состояния
по символу
переходят в класс
,
а состояние 6 – в класс
.
По остальным символам состояния
переходят в один и тот же класс. Состояния
остаются в одном классе. Разбиение
имеет вид
.
Шаг 3. Поскольку
,
полагаем
и идем на шаг 2.
Шаг 2. Сгруппируем состояния в таблице переходов в классы, состояния из различных классов выделим разным шрифтом.
|
|
|
|
y |
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
7 |
7 |
8 |
8 |
7 |
5 |
1 |
3 |
|
6 |
2 |
6 |
2 |
4 |
1 |
8 |
8 |
|
1 |
1 |
3 |
3 |
3 |
1 |
3 |
1 |
Класс
разбивается на два класса:
и
,
поскольку состояния
по символу
переходят в класс
,
а состояния
– в класс
.
Состояния
остаются в одном классе. Разбиение
имеет вид
.
Шаг 3. Поскольку
,
полагаем
и идем на шаг 2.
Шаг 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 |
Ни один класс больше не разбивается.
Шаг 3. Поскольку
,
получено искомое разбиение, которое
совпадает с разбиением из подраздела
2.1.2.
Оценим вычислительную сложность
алгоритма Мура. Каждый раз, кроме
последнего, при выполнении шага 2 число
классов неотличимости увеличивается.
Так как максимальное число классов
неотличимости равно
– числу состояний исходного автомата
,
а на шаге 1 мы получим как минимум один
класс неотличимости, то максимальное
число итераций алгоритма будет
.
Пример. Рассмотрим автомат Мура, для которого число итераций алгоритма будет в точности равно .
Разбиение
состоит из двух классов –
и
.
На первой итерации алгоритма отдельный
класс образует состояние 2, на второй –
состояние 3, и т.д.
Примем за сложность алгоритма число
вычислений функции
.
На каждой итерации мы вычисляем значения
в худшем случае для всех
и
.
Пусть
,
,
тогда сложность не превышает
.
При больших
эта оценка имеет порядок
.