Algorytmy minimalizacji automatów Moore'a

Algorytm Brzozowskiego można rozszerzyć na automaty Moore'a, ale jego złożoność czasowa jest generalnie wykładnicza. Czy istnieje jakiś inny algorytm minimalizacji automatów Moore? Jakie są czasy działania tych algorytmów, jeśli takie istnieją?

Oryginalny algorytm minimalizacji DFA został faktycznie zaprojektowany dla Moore Machines , kierując się ich pozornie bardziej obserwowalnym zachowaniem. Ale przedstawiony tutaj algorytm jest rekonstrukcją z minimalizacji DFA, ponieważ odkryłem dowody historyczne po fakcie.

Po Wikipedii (z pewnymi zmianami notacyjnymi):

Urządzenie Moore można zdefiniować jako 6-krotnego $(Q, q_0, \Sigma, \Pi, \delta, \gamma)$ składający się z następujących elementów:

• skończony zbiór stanów $Q$
• stan początkowy (zwany również stanem początkowym) który jest elementem $q_0$$Q$
• skończony zbiór zwany alfabetem wejściowym $\Sigma$
• skończony zbiór zwany wyjściowym alfabetem $\Lambda$
• funkcja przejścia odwzorowuje stan i alfabet wejściowy na następny stan $\delta : Q \times \Sigma \rightarrow Q$
• funkcja wyjściowa mapuje każdy stan na wyjściowy alfabet $\gamma : Q \rightarrow \Pi$

Zgodnie z tą definicją maszyna Moore'a jest deterministycznym przetwornikiem stanu skończonego.

Nie mam odniesienia do minimalizacji automatów Moore'a. Nie wydaje się jednak zbyt trudne wyobrażenie sobie algorytmu pochodzącego z algorytmu stosowanego do deterministycznych automatów skończonych.

Idea minimalizacji DFA oparta jest na charakterystyce Myhill-Nerode dla zwykłych języków .

Biorąc pod uwagę język , oraz parę ciągów x i y , zdefiniować wyróżniający rozszerzenie być ciągiem oo tak, że dokładnie jeden z dwóch ciągów x Z i Y Z należy do L . Zdefiniować relację R, L na łańcuchach przez zasadę, że x R L R IFF nie wyróżniający rozszerzenie dla x i y . Łatwo jest pokazać, że R L jest relacją równoważności na sznurkach, a więc dzieli zbiór wszystkich ciągów na klasy równoważności.$L$$x$$y$$z$$xz$$yz$$L$$R_L$$x R_L y$$x$$y$$R_L$

Twierdzenie Myhill-Nerode stwierdza, że jest regularne wtedy i tylko wtedy, gdy R L ma skończoną liczbę klas równoważności, a ponadto, że liczba stanów w najmniejszym deterministycznym automacie skończonym (DFA) rozpoznającym L jest równa liczbie klas równoważności w R l .$L$$R_L$$L$$R_L$

Rzeczywiście każdy stan najmniejszej DFA jest takie, że W Q jak zdefiniowano powyżej, jedną z klas równoważności na stosunek R L .$q$$W_q$$R_L$

W przypadku nie-minimalnego DFA dla języka regularnego łatwo jest wykazać, że każdy zestaw W q zawiera łańcuchy, które wszystkie należą do tej samej równoważnej klasy w odniesieniu do R $L$$W_q$$R_L$ .

Zatem minimalizacja DFA faktycznie polega na łączeniu stanów (traktowanych jako zestawy równoważnych ciągów), ilekroć zostanie wykazane, że dwa różne stany zawierają równoważne ciągi.

W tym celu istnieją dwa dość szybkie algorytmy: algorytm Moore'a (1956), który jest w czasie i algorytm Hopcrofta (1971) w czasie O ( n log n $O(n^2)$$O(n\log n)$ .

Przedłużenie Moore automatów jest najlepiej rozumiany w redefining stosunek równoważności, dla przetwornika T . Relacja R L dotyczyła tego, czy przyszłe dane wejściowe doprowadzą w sposób równoważny do stanu akceptującego. R $R_T$$T$$R_L$$R_T$ relacja równoważności z automatów Moore'a dotyczy tego, czy wejście przyszłość przyniesie taki sam efekt.

Stąd, biorąc pod uwagę przetwornik i dwa ciągi x i y , definiujemy rozszerzenie wyróżniające jako ciąg z taki, że T ( x z ) = T ( x ) u i T ( y z ) = T ( y ) v z u ≠ v , tj. takie, że zachowanie wyjściowe przetwornika różni się dla z zależnie od tego, czy następuje po x lub $T$$x$$y$$z$$T(xz)=T(x)u$$T(yz)=T(y)v$$u\neq v$$z$$x$$y$ .

Ponownie, jest relacją równoważności, dzielącą wszystkie łańcuchy na Σ $R_T$$\Sigma^*$ na klasy równoważności. W przypadku maszyny Moore klasy te ponownie będą odpowiadały stanowi minimalnego przetwornika.

Poniższy algorytm naśladuje algorytm Moore'a w celu minimalizacji DFA.

Zdefiniować początkową partycji z Q na klasy stanowi, S e , jak następuje:$\mathcal P$$Q$$S_e$

$\forall e\in\Pi:\; S_e=\{q\in Q\mid \gamma(q)=e\}$

Następnie podzieliliśmy klasy na $\mathcal P$ w następujący sposób:

powtarzaj kolejno dla każdej klasy stanów , aż żadna zmiana nie powtórzy ∀ a ∈ Σ $S$
$\ \ $ $\forall a\in\Sigma,\;$
$\ \ \ \ $ Jeżeli następnienie rób nicwięcej,dzieląc S na podzbiory S i tak, żedla każdego podzbioru S i istnieje inna klasa S ′ ∈ P taka, że ∀ q ∈ S i$\exists S'\in \mathcal P,\; \forall q\in S,\; \delta(q,a)\in S'$
$\ \ \ \ $ $S$$S_i$
$\ \ \ \ \ \ $$S_i$$S'\in \mathcal P$ (podzbiory S i zastępują S w$\forall q\in S_i,\; \delta(q,a)\in S'$
$\ \ \ \ \ \ $$S_i$$S$$\mathcal P$ )

Gdy nie ma już żadnej klasy, którą należałoby podzielić, pozostałe klasy stanów utworzą stany minimalnej maszyny Moore'a.

Z założenia wszystkie stany w klasie mają takie same dane wyjściowe, co dane wyjściowe dla klasy.

Podobnie dla każdego wejścia $a\in\Sigma$ wszystkie stany w klasie przechodzą do pewnego stanu w tej samej innej klasie, która definiuje funkcję przejścia dla minimalnej maszyny Moore'a.

Analiza złożoności: Niech być liczbą stanów, a s = | Σ | wielkość wprowadzanego alfabetu. Główna pętla jest wykonywana co najwyżej n razy, ponieważ każda iteracja musi podzielić co najmniej jedną klasę stanów, a każda klasa zawiera co najmniej jeden stan. Każda iteracja pętli sprawdza każdy stan skończoną liczbę razy i proporcjonalnie do liczby symboli wejściowych. Dlatego złożoność algorytmu wynosi O ( s n 2$n=|Q|$$s=|\Sigma|$
$n$$O(sn^2)$ , tak samo jak algorytm minimalizacji DFA, który posłużył za wskazówkę dla tego algorytmu.

Nie mam odniesienia do tej minimalizacji maszyn Moore. Być może jest to zawarte w jego pracy:

Moore, Edward F. (1956). „Eksperymenty Gedankena na maszynach sekwencyjnych”. Automata Studies , Annals of Mathematical Studies (Princeton, NJ: Princeton University Press) (34): 129-153.

Ten artykuł jest głównym dokumentem wprowadzającym Moore Machines . Jest to również odniesienie do algorytmu minimalizacji DFA Moore'a . Zaskakujące powinno być zatem to, że dostosowanie algorytmu do minimalizacji maszyn Moore'a nie było przynajmniej sugerowane w tym dokumencie. Sprawdziłem gazetę, a przedstawiona wersja algorytmu minimalizacji jest w rzeczywistości dla maszyn Moore, a nie dla DFA. Artykuł jest dobrze napisany, ale styl czasu utrudnia jego czytanie. Interesujące jest to, że wiele pomysłów teorii Myhill-Nerode maszyn skończonych stanów zostało już naszkicowanych w tym artykule.

Nowsza algorytm powodu John Hopcroft (1971) W podobny sposób należy dostosować do urządzeń Moore. Nie jest jasne, że istniał jakikolwiek powód, aby opublikować tę adaptację w dowolnym miejscu, a artykuł Hopcroft wydaje się nie mieć odniesienia do maszyn Moore.$O(sn\log n)$

Wersja algorytmu Brzozowskiego wykorzystująca pochodne wyrażeń regularnych podana jest w [2], rozdziale 12, sekcji 4, gdzie zapisano ją w [4]. Patrz [1] i [3], aby zapoznać się z bardziej ogólnym przypadkiem przetworników podsekwencyjnych (terminologia jest nieco przestarzała, a termin przetwornik sekwencyjny jest obecnie prawdopodobnie bardziej odpowiedni).

[1] C. Choffrut, Minimalizacja podrzędnych przetworników: ankieta, Theoret. Komp. Sci. 292 (2003), 131–143.

[2] S. Eilenberg, Automata, Languages ​​and Machines, vol. A, Academic Press, 1974.

[3] J.-E. Pin, samouczek na temat funkcji sekwencyjnych . (Slajdy)

[4] GN Raney, Funkcje sekwencyjne, JACM 5 (1958), 177–180.

Algorytm Brzozowskiego jest złym punktem wyjścia (jeśli chodzi o asymptotyczne środowisko uruchomieniowe najgorszego przypadku). Nawet Wikipedia mówi ci tyle:

Jak zauważył Brzozowski (1963), odwrócenie krawędzi DFA powoduje niedeterministyczny automat skończony (NFA) do odwrócenia oryginalnego języka i przekształcenie tego NFA w DFA przy użyciu standardowej konstrukcji zestawu mocy (konstruując tylko możliwe do osiągnięcia stany skonwertowany DFA) prowadzi do minimalnego DFA dla tego samego odwróconego języka. Powtórzenie tej operacji odwracania po raz drugi daje minimalny DFA dla oryginalnego języka. Złożoność algorytmu Brzozowskiego w najgorszym przypadku jest wykładnicza, ponieważ istnieją regularne języki, dla których minimalny DFA odwrócenia jest wykładniczo większy niż minimalny DFA języka [6], ale często działa lepiej niż sugerowałby ten najgorszy przypadek.

Algorytm ma wykładniczy czas działania w najgorszym przypadku, nawet w DFA, ponieważ oblicza automat dla odwrotności, który może być wykładniczo duży. Więc twój problem nie pochodzi z rozszerzenia na przetworniki.

Spróbuj dostosować inny algorytm minimalizacji DFA.