Аннотация

Минимизация детерминированного конечного автомата (DFA) является хорошо изученной проблемой формального языка. Эффективный алгоритм для этой проблемы – поставленный Хопкрофом в 1970 году, и мы уже изучили этот алгоритм. Цель этой статьи – обсудить, как этот алгоритм выполняемой во временной сложности O (M Nlog₂ N) (где M – размер алфавита, а N – количество состояний). Статья состоит из трех разделов: сначала мы рассмотрим исходный алгоритм; во-вторых, мы предоставляем соответствующие для эффективного выполнения алгоритма; и наконец мы докажем, что алгоритм действительно во времени O (M Nlog₂ N), используя эти данные структур.

Содержание

1. Введение
2. Структура данных
3. Анализ временной сложности
4. Источники

Введение

Пусть A – детерминированный конечный автомат (Q, A, E, I, F), где Q – бесконечное множество состояний, A – алфавит, E – множество краев перехода, I и F – множества начальных и конечных состояний соответственно. Пусть M – размер алфавита, а N – количество состояний. Для удобства пусть A – множество целых чисел от 1 до M.

Задача минимизации состоит в том, чтобы автомат A' с минимумом число состояний, которое эквивалентно A.

Определение 1. Пусть P – разбиение Q. Число классов в P ограничено N. Следовательно, каждый класс P может иметь право с уникальным именем между 1 и N.

Из определения для каждой пары (C, a), где C – класс, а a – буква, он соответствует уникальному элементу в {1, ..., N} x {1, ..., M}.

Определение 2. Пусть A – детерминированный конечный автомат (Q, A, E, I, F). Пусть a ∈ A и B, C ⊆ Q. Пара (C, a) называется раздельной B, если B · a ⊄ C и B · a ∩ C ≠ 0 с B · a = {x ∈ · a | x ∈ B}. В этом случае B разбивается на (C, a) на две части: B′ = {x ∈ B | x · a ∈ C} и B′′ = {x ∈ B | x · a ∉ C}.

Вспомните алгоритм Хопкрофта:

Минимизация алгоритма Хопкрофта – первая версия ()

1 P ← {F, F^с}

2 S ← ∅ ;

3 for a ∈ A

4 do Insert (min(F, F^с), a) to S

5 while S ≠ ∅

6 do Delete (C, a) from S

7 Decide subset T of P with element split by (C, a)

8 for each B ∈ T

9 do B′, B′′ Split(B,C, a)

10 Replace B by B′ and B′′ in P

11 for b ∈ A

12 do if (B, b) ∈ S

13 then Replace (B, b) by (B′, b) and (B′′, b) in S

14 else Insert (min(B′,B′′), b) to S

2 Структура данных

В этом разделе мы предлагаем несколько структур данных для выполнения алгоритма Хопкрофта.

Пусть Inverse = a^-1 C, что равно {x | a · x ∈ C}. Мы покажем в следующем разделе, что время выполнения цикла while равно O (| Inverse |).

Чтобы достичь эффекта Т, начнем с вычисления приближенного подмножество T′ из P, которое содержит элемент B такой, что B ∩ Inverse ≠ ∅. Это легче получить T′ после сканирования всех элементов в C. В O (1) время проверить является ли элемент в T′ также в T. Таким образом, предыдущий алгоритм можно переписать следующим образом:

Минимизация алгоритма Хопкрофта – вторая версия ()

1 P ← {F, F^с}

2 S ← O;

3 for a ? A

4 do Insert (min(F, F^с), a) to S

5 while S ≠ ∅;

6 do Delete (C, a) from S

7 Inverse ← a ^-1 C

8 Decide subset T′ of P with element B such that B ∩ Inverse ≠ ∅ ;

9 for each B ∈ T′

10 do if B · a ⊄ C

11 then B′, B′′ Split (B,C, a)

12 Replace B by B′ and B′′ in P

13 for b ∈ A

14 do if (B, b) ∈ S

15 then Replace (B, b) by (B′, b) and (B′′, b) in S

16 else Insert (min(B′, B′′), b) to S

Здесь раздел P будет характеризоваться четырьмя массивами Class, Part, Card, Place:

• Класс [x]: имя класса, содержащего состояние x;
• Part [i]: указатель на двусвязный список со всеми состояниями в классе с именем i;
• Card [i]: размер класса с именем i;
• Поместите [x]: указатель на положение состояния x в связанном списке. Часть [p], где p = класс [x].

Структуры выше позволяют нам перемещать состояние из одного класса в другой в O (1).

Целочисленная переменная Counter поддерживает количество классов в P. Это первоначально установлен на 2 (или 1, if F = Q) и увеличивается во время выполнения программа.

Чтобы вычислить Inverse = a^-1 C, мы используем массив Inv, индексированный по {1, ..., N} ∗ {1, ..., M}, что Inv [x, a] является указателем на связанный список состояний y, удовлетворяющих y · a = x. Таким образом, Inverse не нужно строить физически, но только во времени, пропорциональном его размеру, когда мы проходим list Part [Class [C]] и для каждого состояния y в этом списке пересечь Inv [y, a]. Так выражение для всех x ∈ Inverse′′ выполняется как: для всех y ∈ C и всех x ∈ Inv [y, a] .

Список S должен эффективно поддерживать эти операции: вставку, поиск и удалите случайный элемент. Отмечая, что размер S ограничен MN, мы будет использовать связанный список вместе с булевым массивом InList, который индексируется {1, ..., N} ∗ {1, ..., M} (InList [C, a] истинно, если (C, a) ∈ S). Таким образом, вставьте операция выполняется в O (1): вставьте этот элемент в связанный список и обновите его соответствующий значение в InList; операция поиска выполняется в O (1) благодаря InList; операция удаления выполняется в O (1): удалить элемент head из связанного списка и обновить его соответствующее значение в InList; наконец, проверить, S ≠ ∅ является также выполняется в O (1) из-за структуры связанного списка.

Чтобы получить T′, мы используем следующие три структуры дат:

• Involved: связанный список имен классов в T′;
• Size: целочисленный массив, такой, что для каждого класса B с именем i Size[i] является мощность B ∩ а^-1 С. Этот массив должен быть очищен до 0 каждый раз, пока выполняется цикл;
• Twin: целочисленный массив, так что Twin [i] – это имя созданного нового класса разделяя класс с именем i. Этот массив также должен быть инициализирован каждый время выполнения цикла while.

3 Анализ временной сложности

Теперь мы проанализируем временную сложность алгоритма Хопкрофта второй версии выше. Здесь нас интересует только временная сложность, а не забота о сложности пространства.

Лемма 3. Количество классов, созданных во время выполнения, ограничено 2N - 1. Кроме того, число итераций цикла while ограничено 2MN.

Доказательство. Рассмотрим двоичное дерево, которое соответствует разделенным операциям что каждый узел является подмножеством Q. Корнем дерева является все множество Q. Это имеет двух детей, а их объединение равно Q. Каждый нелистный узел P в этом дерево имеет двух детей P′ и P′′, что является результатом примененной операции разделения к P. Такое двоичное дерево имеет не более N листьев, поэтому не более 2N - 1 узлов, поэтому мы докажем первую половину леммы. Чтобы связать количество итерации цикла while, достаточно доказать, что число пар (C, a) вставленный в S, ограничен 2MN, потому что на каждой итерации мы удаляем пару из S. Рассмотрим некоторую пару (C, a), вставленную в S. Здесь C – элемент тока раздел и соответствует некоторому узлу в двоичном дереве выше, поэтому выбор C имеет не более 2N - 1 различных возможностей; и поскольку выбор a имеет разные возможности, заключаем, что число пар (С, а) ограничено на 2МН.

Инициализация до цикла while во времени O (MN). Количество итерации цикла while ограничены 2MN (по лемме 3), поэтому глобальное выполнение время линии 6 равно O (MN). И количество созданных классов ограничено на 2N -1 (также по лемме 3), поэтому глобальное время выполнения строки 13 по строке 16 O (MN)

Он только оценивает глобальное время выполнения строки 7 по строке 12. В порядке для этого мы делаем два шага: сначала оцениваем сумму | Inverse | во всех исполнениях цикла while (эта сумма отмечена как ∑ | Inverse | с этого момента), а затем что глобальное время выполнения от строки 7 до строки 12 равно O ( ∑ | Inverse |).

ПРЕДЛОЖЕНИЕ 4. Пусть a ∈ A, p ∈ Q. Сколько раз мы Delete (C, a) из списка S, удовлетворяющее p ∈ C, ограничено log₂N.

Доказательство. Мы называем пару (C, a) обозначаемой, если p ∈ C. До цикла while S содержит не более одной отмеченной пары (это условие выполняется для всех экземпляров a и p). Пусть (C, a) – первая отмеченная пара, которая удаляется из S. Если существует вторую отмеченную пару (C′′, a), то перед Delete (C′′, a) должна быть некоторая пара (C′, a), который генерируется k. Заменяйте операции, начиная с пары (C, a) (k ≥ 0), что (C′′, a) является результатом Split (C′, a). Итак, Card (C′) ≤ Card (C) и карты (C′′) ≤ Card (С′) / 2. Теперь возьмем (C′′, a) как (C, a) и повторим в так же, пока не произойдет такая операция удаления. Таким образом, число таких операции удаления не более чем log₂n для пары p и a.

Следствие 5. Сумма | Inverse | во всем выполнении цикла while ограничен по MNlog₂N.

Доказательство. Пусть (x, a, y) – трехмерный триплет, удовлетворяющий y = x · a. Количество раз что x читается в списке. Обратное, удовлетворяющее y = x · a, точно такое же, как количество пар (C, a), удаленных из списка S, таких, что y ∈ C. Из Предложение 4, это число ограничено log₂N, поэтому мы докажем следствие. Чтобы показать, что глобальное время выполнения строки 7 по строке 12 O (∑ | Inverse |), мы выполняем эту часть алгоритма следующим образом: перемещение связанного списка Inverse twice

Минимизация алгоритма Хопкрофта – вторая-версия-упрощенная ()

1 create an empty list Involved

2 for all y ∈ C and all x ∈ Inv[y, a]

3 do i ← Class[x]

4 if Size[i] = 0

5 then Size[i] ← 1

6 insert i to Involved

7 else Size[i] ← Size[i] + 1

8 for all y ∈ C and all x ∈ Inv[y, a]

9 do i ← Class[x]

10 if Size[i] < Card[i]

11 then if Twin[i] = 0

12 then Counter ← Counter + 1

13 Twin[i] ← Counter

14 delete x from class i and insert x into class Twin[i]

15

16 for all j ∈ Involved

17 do Size[j] ← 0

18 Twin[j] ← 0

Сверху ясно, что время выполнения этой части за один цикл - O (| Inverse |), поэтому глобальным временем выполнения этой части является O (∑ | Inverse |).

Теорема 6. Пусть A – алфавит из M букв, а A – DFA на этом алфавите с N состояниями, то алгоритм Хопкрофта, использующий структуры данных в предыдущем секция находится во времени O (MNlog₂N) в худшем случае.

Замечание. Эта сложность также плотная, что подробно доказывается в [2].

Список использованной литературы

1. Beauquier D., Berstel J., Chretienne Elements d'algorithmique P. / D. Beauquier, J. Berstel, P. Chretienne. Masson. – 1992.
2. Berstel J., Carton O. On the complexity of hopcroft's state minimization algorithm / J. Berstel and O. Carton. CIAA. – 2004.
3. Aho A., Hopcroft J., Ullman J. The Design and Analysis of Computer Algorithms / A. Aho, J. Hopcroft, and J. Ullman // Addison-Wesley. – 1974.