Uogólnienie algorytmu minimalizacji DFA Brzozowskiego do automatów skończonych z różnymi klasami stanów akceptujących?

9

Algorytm Brzozowskiego do przekształcania DFA w równoważny DFA stanu minimalnego jest niezwykle prosty: jeśli oznacza NFA utworzony przez odwrócenie wszystkich krawędzi w DFA , czyniąc stary stan początkowy stanem akceptującym i czyniąc starym akceptowaniem stwierdza początek stanów i jeżeli oznacza wynik zastosowania konstrukcji podzbioru do NFA , a następnie jest co najmniej w stanie DFA z tym samym języku jak .R(re)reP.(N.)N.

P.(R(P.(R(re))))
re

Możemy myśleć o DFA jako urządzeniu obliczeniowym, które akceptuje łańcuch wejściowy a następnie wyprowadza 0, jeśli kończy się w stanie odrzucającym, a 1, jeśli kończy się w stanie akceptującym. Naturalne uogólnienie DFA wiązało każdy stan w DFA z pewną liczbą naturalną od 0 do włącznie.wwwk-1

Według mojej najlepszej wiedzy, możliwe jest zminimalizowanie tych zmodyfikowanych klas DFA przy użyciu algorytmu minimalizacji opartego na rozróżnialności, takiego jak kanoniczny algorytm Hopcroft. Nie widzę jednak, jak byłoby możliwe dostosowanie algorytmu minimalizacji Brzozowskiego do tej nowej klasy automatów, ponieważ kluczowy krok (odwrócenie automatu) nie ma już jasnej interpretacji w tym uogólnionym ustawieniu.

Czy znane jest uogólnienie algorytmu Brzozowskiego do minimalizowania tego rodzaju automatów? Jeśli nie, czy istnieją jakieś teoretyczne powody, dla których spodziewalibyśmy się, że taki zmodyfikowany algorytm nie istniałby?

automata-theory minimization templatetypedef
źródło
„uogólnienie” nie wydaje się być jasno zdefiniowane. co jestk? czy chodzi tylko o powiązanie każdego stanu w DFA z ograniczoną liczbą całkowitą? co wtedy? jaki jest przykład kto z tym pracuje? itp
vzn
@vzn Możesz myśleć o każdym stanie w normalnym DFA jako powiązanym z 0 lub 1 (odpowiednio stany odrzucenia i zaakceptowania). Myślę o uogólnieniu tego na przypadek, w którym każdy stan DFA jest powiązany z pewną wartością w{0,1,2),3),...,k-1}, a DFA wyprowadza liczbę związaną ze stanem, w którym ciąg się kończy.
templatetypedef
ok, w ogóle nie jest to podane w poście, „DFA wyprowadza # związany ze stanem, w którym kończy się łańcuch”, sugeruje to naprawić. ponadto DFA technicznie nie mają „wyjścia”. może masz na myśli przetwornik FSM? rzeczywiście istnieje jakaś częściowa teoria związana z minimalizacją przetwornika FSM, która najwyraźniej nie jest („jeszcze”?) w pełni powiązana z minimalizacją DFA.
vzn

Odpowiedzi:

7

Odpowiedź na twoje pytanie brzmi: tak.

Zobacz prace Bonchi, Bonsangue, Rutten i Silvy Algorytm Brzozowskiego (co) algebraicznie (krótsza wersja konferencyjna) i Algebra-Coalgebra Duality w algorytmie minimalizacji Brzozowskiego (dłuższa wersja czasopisma z większą liczbą uogólnień).

Dają (lekko) kategoryczną prezentację algorytmu Brzowzowskiego i wykorzystują go do uzyskania jego wersji dla bardziej ogólnych klas automatów, w tym automatów Moore'a (co daje pozytywną odpowiedź na twoje pytanie).

Neel Krishnaswami
źródło
6

Aby dodać do odpowiedzi Neela, w mojej książce Automatic Sequences with Jean-Paul Allouche omawiamy DFAO (deterministyczne automaty skończone z wyjściami), o które dokładnie pytałeś (kojarz wyjście z każdym stanem). A Twierdzenie 4.3.3 opisuje, jak odwrócić taką maszynę.

Jeffrey Shallit
źródło