Minimalizowanie automatów akceptujących słowa (tj. Nieskończone słowa)

Jakie jest standardowe podejście do minimalizacji Büchi-Automata (lub także Müller-Automata)? Przeniesienie zwykłej techniki ze słów skończonych, tj. Ustawienie dwóch stanów na równe, jeśli słowa „wyczerpania” stanów, które są akceptowane, są takie same, nie zadziała. Na przykład rozważmy, że Büchi-Automoton akceptuje wszystkie słowa o nieskończonej liczbie a, składające się z dwóch stanów, stanu początkowego i końcowego, a stan końcowy jest wprowadzany za każdym razem, gdy czytany jest a, a stan początkowy jest wprowadzany za każdym razem czytany jest inny symbol. Oba stany są uważane za równe na podstawie powyższej definicji, ale ich zwinięcie daje automaty składające się z jednego stanu, a tym samym akceptują każde słowo.

Ogólnie rzecz biorąc, nieregularne języki mogą nie mieć unikalnej minimalnej DBW. Na przykład język „nieskończenie wiele a i nieskończenie wiele b” ma dwa 3-stanowe DBW (na zdjęciu zamień na ): ¬ a $\omega$$\neg a$$b$

Jak widać, nie są one topologicznie równoważne.

W związku z tym problem minimalizacji jest trudniejszy niż przypadek skończony, a w rzeczywistości jest NP-zupełny .

To pytanie wygenerowało dużą literaturę w latach 80-tych, częściowo z powodu złego podejścia do problemu. To raczej długa historia, którą postaram się streścić w tej odpowiedzi.

1. Przypadek słów skończonych

W literaturze można znaleźć dwie definicje minimalnego DFA. Pierwszym jest zdefiniowanie minimalnego DFA zwykłego języka jako pełnego DFA z minimalną liczbą stanów akceptujących ten język. Drugi jest dłuższy do zdefiniowania, ale matematycznie bardziej atrakcyjny niż pierwszy i daje silniejsze właściwości.

Przypomnijmy, że DFA jest dostępny, jeśli dla wszystkich znajduje się słowo tak że . Jest to kompletny jeśli określony dla wszystkich a .q ∈ Q u ∈ A ∗ i ⋅ u = q q ⋅ a q ∈ Q a ∈ $(Q, A, \cdot, i, F)$$q \in Q$$u \in A^*$$i \cdot u = q$$q \cdot a$$q \in Q$$a \in A$

Niech i będą dwoma kompletnymi, dostępnymi DFA. Morfizm od do to funkcja taka, że${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$${\cal A}_2 = (Q_2, A, \cdot, i_2, F_2)$$\mathcal{A}_1$$\mathcal{A}_2$$\varphi:Q_1 \to Q_2$

1. $\varphi(i_1) = i_2$ ,
2. $\varphi^{-1}(F_2) = F_1$ ,
3. dla wszystkich i , . a ∈ A φ ( q ) ⋅ a = φ ( q ⋅ a $q \in Q_1$$a \in A$$\varphi(q)\cdot a=\varphi(q\cdot a)$

Można wykazać, że warunki te sugerują, że jest z konieczności podejrzany (a zatem ). Ponadto istnieje co najwyżej jeden morfizm od do a jeśli ten morfizm istnieje, wówczas i rozpoznają ten sam język. Teraz można pokazać, że dla każdego języka istnieje unikalny kompletny dostępny DFA akceptujący i taki, że dla każdego kompletnego dostępnego DFA akceptującego występuje morfizm od do | Pytanie 2 | ⩽ | Pytanie 1 $\varphi$$|Q_2| \leqslant |Q_1|$A 2 A 1 A 2 L A L LALA A L L A L A A${\cal A}_1$${\cal A}_2$${\cal A}_1$${\cal A}_2$$L$${\cal A}_L$$L$$\cal A$$L$$\cal A$${\cal A}_L$. Ten automat nazywany jest minimalny DFA z . Zauważ ponownie, że ponieważ liczba stanów w jest mniejsza niż liczba stanów w , jest również minimalna w pierwszym sensie.$L$${\cal A}_L$$\cal A$${\cal A}_L$

Warto wspomnieć, że istnieje również odpowiednia definicja algebraiczna dla niekompletnych DFA. Patrz [Eilenberg, Automata, Languages ​​and Machines , vol. A, Academic Press, 1974] po więcej szczegółów.

2. Powrót do nieskończonych słów

Rozszerzenie pierwszej definicji nie działa, jak pokazuje Shaull w swojej odpowiedzi. I niestety można również wykazać, że uniwersalna właściwość drugiej definicji nie rozciąga się na nieskończone słowa, z wyjątkiem kilku szczególnych przypadków.

Czy to koniec historii? Chwileczkę, jest jeszcze jeden minimalny obiekt, który akceptuje zwykłe języki ...

3. Podejście syntaktyczne

Wróćmy najpierw do skończonych słów. Przypomnijmy, że język z jest rozpoznawana przez monoid , jeśli jest suriekcją monoid morfizmem i podzbiór na taki, że . Ponownie istnieje monoid , zwany składniowym monoid z , który rozpoznaje i jest ilorazem wszystkich monoids rozpoznających . Ten składniowy monoid można zdefiniować bezpośrednio jako iloraz przez zgodność składniową zA ∗ M f : A ∗ → M P M f - 1 ( P ) = L M ( L $L$$A^*$ $M$$f:A^* \to M$$P$$M$$f^{-1}(P) = L$$M(L)$L L A ∗ ∼ L L u ∼ L v  wtedy i tylko wtedy, gdy dla wszystkich  x , y ∈ A ∗ ,  x u y ∈ $L$$L$$L$$A^*$ $\sim_L$$L$, zdefiniowane w następujący sposób: Dobra wiadomość jest taka, że tym razem podejście to zostało rozszerzone na nieskończone słowa, ale dużo czasu zajęło odkrycie odpowiednich pojęć. Po pierwsze, odpowiednie pojęcie zgodności syntaktycznej zostało znalezione przez A. Arnolda ( Kompaktyczna zgodność dla języków racjonalnych , Theoret. Comput. Sci. 39 , 2-3 (1985), 333–335). Rozszerzenie monoidów składniowych na ustawienie nieskończonych słów wymagało bardziej wyrafinowanego rodzaju algeb, zwanych obecnie algebrami Wilke na cześć T. Wilke, który jako pierwszy je zdefiniował (T. Wilke, Teoria algebraiczna dla regularnych języków skończonych i nieskończonych słowa,

4. Wniosek

Zatem istnieje matematyczne uzasadnienie minimalnego obiektu akceptującego dany język regularny , ale nie opiera się on na automatach. W rzeczywistości jest to dość ogólny fakt: automaty są bardzo potężnym narzędziem algorytmicznym, ale nie zawsze są wystarczające, aby traktować matematyczne pytania dotyczące języków.$\omega$