Algorytm Brzozowskiego do minimalizacji DFA

Algorytm minimalizacji DFA Brzozowskiego buduje minimalny DFA dla DFA poprzez:$G$

1. odwrócenie wszystkich krawędzi w , czyniąc stan początkowy stanem akceptacyjnym, a stanami początkowymi początkowymi, aby otrzymać NFA N ' dla języka odwrotnego,$G$$N'$
2. używając konstrukcji powerset, aby uzyskać dla języka odwrotnego,$G'$
3. odwrócenie krawędzi (i zamiana początkowej akceptacji) w aby uzyskać NFA N dla języka oryginalnego, oraz$G'$$N$
4. robienie konstrukcji powerset, aby uzyskać .$G_{\min}$

Oczywiście, ponieważ niektóre DFA mają wykładniczy duży odwrotny DFA, ten algorytm działa w wykładniczym czasie w najgorszym przypadku pod względem wielkości wejścia, więc pozwala śledzić rozmiar odwrotnego DFA.

Jeśli jest rozmiarem wejściowego DFA, n jest rozmiarem minimalnego DFA, a m rozmiarem minimalnego odwrotnego DFA, to jaki jest czas działania algorytmu Brzozowskiego w kategoriach N , n i m ?$N$$n$$m$$N$$n$$m$

W szczególności, w jakich związek między i m robi algorytmy algorytm Brzozowskiego przewyższają Hopcroft użytkownika lub Moore'a?$n$$m$

Słyszałem, że w typowych przykładach w praktyce / zastosowaniu algorytm Brzozowskiego przewyższa inne. Nieoficjalnie, jakie są te typowe przykłady?

Oto częściowa odpowiedź na twoje trzecie pytanie. W rzeczywistości być może algorytm Brzozowskiego naprawdę nie przewyższa wszystkich innych algorytmów tak wyraźnie w minimalizacji DFA.

W [1] autorzy badają praktyczną wydajność algorytmów minimalizacji DFA / NFA. Algorytmy to Hopcrofta, Brzozowskiego i dwa warianty Watsona. Stwierdzili, że nie ma wyraźnego zwycięzcy, ale algorytm Hopcroft działa lepiej w przypadku DFA z małymi alfabetami. Dla NFA Brzozowski jest zdecydowanie najszybszy.

Sam artykuł jest dość krótki i wyraźnie napisany. Są też dodatkowe dyskusje i referencje, które mogą być pomocne.

[1] Almeida M., Moreira N. i Reis R. O wydajności algorytmów minimalizacji automatów, czwarta konferencja nt. Obliczalności w Europie, czerwiec 2008 r.

Większość z nich pochodzi z teorii analizy składni Sippu i Soisalon-Soininen.

Niech będzie zbiorem stanów DFA. Niech T będzie alfabetem wejściowym. Niech | M | = O ( | T | ⋅ | Q | ) jest rozmiarem maszyny. Ćwiczenie 3.40 daje algorytm O ( | T | ⋅ | Q | 2 ) do minimalizacji stanu. Jak opisano w Wikipedii , algorytm Hopcrofta ma czas działania O ( | T | ⋅ | Q | ⋅ $Q$$T$$|M|=O(|T| \cdot |Q|)$$O(|T|\cdot|Q|^2)$ a algorytm Moore'a ma czas działania O ( | T | 2 ⋅ | Q | ) .$O(|T| \cdot |Q| \cdot \log|T|)$$O(|T|^2 \cdot |Q|)$

Twierdzenie 3.30 stwierdza, że ​​budowę podzbioru można wykonać w uzyskując automat o rozmiarze O ( 2 | T | + log | Q | ) (właściwie jeśli wynikowy automat ma stany | T ′ | czas działania wynosi ( | T ′ | + | T | ⋅ |$O(2^{|T|+\log|T|+\log|Q|})$$O(2^{|T|+\log|Q|})$$|T'|$$(|T'| + |T|\cdot|M|) \cdot |Q|$

Oznacza to, że w najgorszym przypadku algorytm Brzozowskiego jest wykładniczo wolniejszy niż pozostałe trzy algorytmy. Zauważ, że najgorszy przypadek naprawdę się zdarza: klasyczny przykład NFA dla języka ma stany k + 1 , a odpowiadający mu minimalny DFA ma stany O ( 2 k ) , podczas gdy odwrotność NFA jest deterministyczne, więc uruchomienie algorytmu Brzozowskiego na odwróconym NFA wyzwala zachowanie w najgorszym przypadku.$(a|b)^*a^k$$k+1$$O(2^k)$

Jeśli jednak konstrukcja podzbioru daje automaty wielkości , wówczas jego czas działania wynosi również O ( | T | 2 ⋅ | Q | 2 ) , co często ma miejsce w przypadku rzeczywistych danych wejściowych. Ponadto, jeśli przy obliczaniu zamknięcia stanu zachowana zostanie odpowiednia ostrożność, można to zrobić znacznie szybciej w większości przypadków (to znaczy w przypadkach, gdy zamknięcie jest małe), oszczędzając czynnik | T $|T'|=O(|T|)$$O(|T|^2 \cdot |Q|^2)$$|T|$$|Q|$$O(|T| \cdot |Q|)$

$O(|T| \log \log |T|)$ running time in some cases, which would make the three algorithms comparable.

De Felice and Nicaud show that Brzozowski's algorithms is asymptotically hyper-polynomial. David has shown that, for several distributions on final states, Hopcroft's algorithm is slower that Moore's algorithm.

References

S. De Felice and C. Nicaud, "Brzozowski Algorithm is Generically Super-Polynomial for Deterministic Automata". In Proceedings of 17th International Conference on Developments in Language Theory (DLT 2013), Lecture Notes in Computer Science, pp. 170–190, 2013. (PDF)

J. David, "Average complexity of Moore’s and Hopcroft’s algorithms". Theoretical Computer Science, 417:50–65, 2012. (Science Direct)