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,q0,Σ,Π,δ,γ) 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 Qq0Q
- skończony zbiór zwany alfabetem wejściowym Σ
- skończony zbiór zwany wyjściowym alfabetem Λ
- funkcja przejścia odwzorowuje stan i alfabet wejściowy na następny stan δ:Q×Σ→Q
- funkcja wyjściowa mapuje każdy stan na wyjściowy alfabet γ:Q→Π
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.LxyzxzyzLRLxRLyxyRL.
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.RL.L.RL.
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 .qW.qRL.
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 LL.W.qRL. .
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 ( n2))O ( n logn ) .
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 TRT.TRLRT 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 yTxyzT(xz)=T(x)uT(yz)=T(y)vu≠vzxy .
Ponownie, jest relacją równoważności, dzielącą wszystkie łańcuchy na
Σ ∗RTΣ∗ 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:PQSe
∀e∈Π:Se={q∈Q∣γ(q)=e}
Następnie podzieliliśmy klasy na P w następujący sposób:
powtarzaj kolejno dla każdej klasy stanów , aż żadna zmiana nie powtórzy ∀ a ∈ Σ ,S
∀a∈Σ,
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 ,∃S′∈P,∀q∈S,δ(q,a)∈S′
SSi
SiS′∈P (podzbiory S i zastępują S w P∀q∈Si,δ(q,a)∈S′
SiSP )
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∈Σ 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=|Σ|
nO(sn2) , 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(snlogn)