2.1.4. Построение классов неотличимости: алгоритм Хопкрофта
Рассмотрим алгоритм, более эффективный в вычислительном плане, чем алгоритм Мура, но, возможно, более сложный для понимания.
Определение. Обратной функцией переходов конечного автомата назовем функцию вида
,
т.е. значением обратной функции переходов является множество состояний, которые переходят по заданному символу в заданное состояние.
Пример. Рассмотрим автомат из предыдущего подраздела
|
|
|
|
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 |
Обратная функция переходов для него имеет вид
|
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
7 |
|
8 |
|
6 |
|
1,2,5 |
3,4 |
|
6 |
2,4 |
|
5 |
|
1,3 |
|
7,8 |
|
1,2,6,8 |
|
3,4,5,7 |
|
|
|
|
|
Обратная функция переходов очевидным образом может быть распространена на множества:
.
Идея алгоритма Хопкрофта состоит в следующем. Разбиение на классы неотличимости обладает следующими двумя свойствами:
столбцы таблицы выходов состояний из одного блока разбиения одинаковы;
по любому входному символу все состояния одного блока переходят в состояния, также принадлежащие одному и тому же блоку.
Начиная с некоторого стартового разбиения (например, можно взять разбиение из алгоритма Мура) строится разбиение, обладающее такими свойствами. Для этого рассматриваются поочередно пары, состоящие из входного символа и блока разбиения, и каждый блок разбивается на два по следующему правилу: в одно множество помещаются состояния, которые переходят по заданному символу в заданный блок, в другое – остальные состояния. Процесс продолжается, пока порождаются новые разбиения.