Znalezienie maksymalnej faktoryzacji zwykłych języków

Niech język będzie regularny.$\mathcal{L} \subseteq \Sigma^*$

Rozkład na czynniki to maksymalna para zestawów słów z ( X , Y $\mathcal{L}$$(X,Y)$

• $X \cdot Y \subseteq \mathcal{L}$
• $X \neq \emptyset \neq Y$ ,

gdzie | .x ∈ X , y ∈ Y $X \cdot Y = \{xy$$x \in X, y \in Y\}$

$(X,Y)$ jest maksymalne, jeśli dla każdej pary z albo lub Y \ nie \ subseteq Y ' .$(X',Y') \neq (X,Y)$$X'\cdot Y' \subseteq \mathcal{L}$$X \not \subseteq X'$$Y \not \subseteq Y'$

Czy istnieje prosta procedura, aby dowiedzieć się, które pary są maksymalne?

Przykład:

Niech $\mathcal{L} = \Sigma^∗ab \Sigma^∗$ . Zestaw $F = \{u, v, w\}$ jest obliczany:

• $u =(\Sigma^∗, \Sigma^∗ab\Sigma^∗)$

• $v = (\Sigma^∗a\Sigma^∗, \Sigma^∗b\Sigma^∗)$

• $w = (\Sigma^∗ab\Sigma^∗, \Sigma^∗)$

gdzie $\Sigma = \{a,b\}$ .

Inny przykład:

$\Sigma = \{a, b\}$ i $\mathcal{L} = \Sigma^*a\Sigma$ Zestaw faktoryzacji $F = \{q, r, s, t\}$ z

• $q = (\Sigma^*, \mathcal{L})$

• $r = (\Sigma^*a, \Sigma + \mathcal{L})$

• $s = (\Sigma^*aa, \epsilon + \Sigma + \mathcal{L})$

• $t = (\mathcal{L}, \epsilon + \mathcal{L})$

Jak zasugerowano w komentarzach do pytania, postaram się udzielić (niestety częściowej) odpowiedzi na pytanie, przynajmniej w takim stopniu, w jakim sam zrozumiałem problem (oznacza to, że możesz znaleźć błędy, a jeśli znajdziesz) sposób na zwięzłe lub wyraźniejsze wyjaśnienie jednego z poniższych punktów, możesz odpowiednio edytować odpowiedź):

Po pierwsze, należy zauważyć, że tak naprawdę nie musimy obliczać uniwersalnego automatu języka, jeśli chcemy obliczyć faktoryzacje języka.

Z artykułu wspomnianego w moim komentarzu ¹ istnieje zgodność 1-1 między lewymi i prawymi czynnikami zwykłego języka, to znaczy, biorąc pod uwagę lewy czynnik języka, odpowiedni prawy czynnik jest jednoznacznie określony i odwrotnie. Dokładniej, mamy następujące:

Niech być na czynniki . Wtedy to znaczy, że każdy lewy czynnik jest przecięciem prawych ilorazów, i każdy właściwy czynnik to przecięcie lewych ilorazów. Z drugiej strony, każdy punkt przecięcia lewych ilorazów jest tuż czynnik , a każdy punkt przecięcia prawych ilorazów jest lewy czynnik .$(X,Y)$$L$

Zauważ, że w przypadku zwykłego języka istnieje tylko skończony zestaw lewych i prawych ilorazów, a zatem problem sprowadza się do obliczenia lewego i prawego ilorazu języka, a następnie do obliczenia ich stabilnego zamknięcia, czyli minimalny nadzbiór ilorazów, który jest zamknięty na przecięciu. Są wtedy właśnie odpowiednie czynniki i pozostawione czynników, a to jest zwykle łatwo zobaczyć, które pary są podzbiory .$\cap$$L$

Przykład

Aby zilustrować powyższe punkty, rozważ pierwszy przykład w pytaniu (którego również uważam za niepoprawny w pracy):

Niech . Teraz lewe ilorazy to zbiory dla , to znaczy te słowa w które mogą być poprzedzone , tj. . Kiedy dla odrębnego ? Tak jest w przypadku, jeżeli i tylko jeżeli i mogą być zwiększone do słowa$L = \Sigma^\ast ab \Sigma^\ast$$L$$x^{-1}L$$x\in \Sigma^\ast$$u$$\Sigma^\ast$$x$$xu \in L$$y^{-1}L=x^{-1}L$$x,y$$x$$y$$L$z dokładnie tymi samymi przyrostkami. Oznacza to, że mówiąc bardziej znajomo, są one odpowiednikami Nerode, a przyrostki potrzebne do dołączenia do słów w klasie Nerode są dokładnie odpowiednimi lewymi ilorazami.

Dla widzimy, że nasze klasy równoważności Nerode są$L$

• $N_1$ , zestaw słów niezawierających jako czynnika i kończących się , $ab$$a$
• $N_2$ , zestaw słów kończących się na i niezawierających jako czynnika, oraz $b$$ab$
• $N_3$ , zbiór słów zawierających jako czynnik, to znaczy$ab$$N_3 = L$

Można je uzupełnić o następujące zestawy (to są lewe ilorazy słów w odpowiednich klasach):

• $S_1 = x^{-1}L$ dla w składa się ze wszystkich słów w (każde słowo może być uzupełnione słowem zawierającym jako czynnik, a zatem staje się słowem w ) i , że to$x$$N_1$$L$$ab$$L$$b\Sigma^\ast$$S_1 = L \cup b\Sigma^\ast$
• $S_2 = x^{-1}L$ dla w to sam język, to znaczy i$x$$N_2$$S_2 = L$
• $S_3 = x^{-1}L$ dla w to oczywiście . Oznacza to, że udało nam się znaleźć trzy odpowiednie czynniki . Ponieważ , ich stabilne zamknięcie jest trywialne , a zatem są to właśnie właściwe czynniki.$x$$N_3$$\Sigma^\ast$$L$$S_2\subset S_1\subset S_3$$\cap$${S_1,S_2,S_3}$

Stąd nasz zestaw faktoryzacji ma postać .$\mathcal{F}_L$$(P_1,S_1),(P_2,S_2),(P_3,S_3)$

Teraz, dla lewych czynników , używamy równań z początku tej odpowiedzi:$P_i$

Dla , to plony dla otrzymujemy i otrzymujemy . Możesz to zobaczyć przez inspekcję (najpopularniejsze usprawiedliwienie dla bycia zbyt leniwym, aby podać formalny dowód) lub przez jawne obliczenie właściwych ilorazów (co jest dość analogiczne, choć nie całkowicie, do obliczenia lewych ilorazów). Nasze faktoryzacje są więc podane przez gdzie$P_1$$L \cup \Sigma^\ast a$$P_2$$\Sigma^\ast$$P_3$$L$$\mathcal{F}_L = {u,v,w}$

• $u = (P_1,S_1) = (\Sigma^\ast ab \Sigma^\ast \cup \Sigma^\ast a, \Sigma^\ast ab \Sigma^\ast \cup b\Sigma^\ast)$
• $v = (P_2, S_2) = (\Sigma^\ast, \Sigma^\ast ab \Sigma^\ast)$ i
• $w = (P_3, S_3) = (\Sigma^\ast ab \Sigma^\ast, \Sigma^\ast)$

streszczenie

Podsumowując (tak jak prosiłeś o prostą procedurę):

• Do obliczania factorizations języka , najpierw obliczyć lewo ilorazy .$L$$L$
• Można to zrobić w języku artykułu, konstruując minimalny DFA dla a następnie dla każdego stanu w (odpowiadającego jako klasa równoważności Nerode lewemu ilorazowi) obliczyć przyszłość w , uzyskując w ten sposób jeden lewy iloraz języka dla każdego stanu.$A$$L$$q$$A$$q$$A$
• Zbiór lewych ilorazów uzyskanych w ten sposób daje ogólnie podzbiór właściwych czynników.$S_R$
• Oblicz wówczas -stabilny zamknięcie , które mogą być stosowane w praktyce przez wykonanie przecięcia każdego podzbioru i dodawania podzestawu otrzymanej w ten sposób do .$\cap$$S_R$$S_R$$S_R$
• Zestaw wraz ze wszystkimi skrzyżowaniami z poprzedniego etapu jest to zbiór odpowiednich czynników .$S_R$$L$
• W celu uzyskania lewego czynniki, możemy obliczyć odpowiednie ilorazy .$L$
• Są to zestawy postaci , dla . Teraz jest ich znowu tylko skończonych wiele, a dla mamy wtedy i tylko jeśli dla wszystkich , , to znaczy, że mogą być poprzedzone słowami w języku za pomocą dokładnie tego samego zestawu ciągów.$Ly^{-1}$$y\in \Sigma^\ast$$x\neq y$$Ly^{-1} = Lx^{-1}$$u\in \Sigma^\ast$$ux \in L \Leftrightarrow uy \in L$
• Aby obliczyć , rozważ te stany w , że jest zawarty w przyszłości . Zjednoczenie przeszłości tych państw stanowi jeden właściwy iloraz. Znajdź wszystkie te ilorazy.$Lx^{-1}$$q$$A$$x$$q$
• Wiesz, że skończyłeś, gdy znalazłeś tyle lewych czynników, ile masz prawych czynników.
• Znaleźć te pary lewej i prawej strony czynników takie, że . To jest .$X,Y$$X\cdot Y \subseteq L$$\mathcal{F}_L$

1. Uniwersalny automat Lombardii i Sakarowicza (w tekstach z logiki i gier, tom 2: Logika i automaty: historia i perspektywy , 2007)