Ermittlung der maximalen Faktorisierung regulärer Sprachen

Lassen Sie die Sprache $\mathcal{L} \subseteq \Sigma^*$ regelmäßig.

Eine Faktorisierung von $\mathcal{L}$ ist ein maximales Paar $(X,Y)$ von Wortmengen mit

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

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

$(X,Y)$$(X',Y') \neq (X,Y)$$X'\cdot Y' \subseteq \mathcal{L}$$X \not \subseteq X'$$Y \not \subseteq Y'$

Gibt es ein einfaches Verfahren, um herauszufinden, welche Paare maximal sind?

Beispiel:

Es sei . Die Menge wird berechnet: F = { u , v , w $\mathcal{L} = \Sigma^∗ab \Sigma^∗$$F = \{u, v, w\}$

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

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

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

Dabei ist .$\Sigma = \{a,b\}$

Ein anderes Beispiel:

$\Sigma = \{a, b\}$ und Faktorisierungsmenge mitF = { q , r , s , t $\mathcal{L} = \Sigma^*a\Sigma$$F = \{q, r, s, t\}$

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

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

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

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

Wie in den Kommentaren zur Frage vorgeschlagen, werde ich versuchen, eine (leider teilweise) Antwort auf die Frage zu geben, zumindest in dem Maße, in dem ich das Problem selbst verstanden habe (dies impliziert, dass Sie möglicherweise Fehler finden und wenn Sie Fehler finden Wenn Sie einen der folgenden Punkte kurz oder klar erläutern möchten, können Sie die Antwort auch entsprechend bearbeiten.):

Erstens sollte man beachten, dass wir den universellen Automaten einer Sprache nicht berechnen müssen, wenn wir die Faktorierungen einer Sprache berechnen wollen.

Aus dem in meinem Kommentar1 erwähnten Artikel ergibt sich eine 1: 1-Entsprechung zwischen dem linken und dem rechten Faktor einer regulären Sprache, dh bei einem linken Faktor der Sprache ist der entsprechende rechte Faktor eindeutig bestimmt und umgekehrt. Genauer gesagt haben wir Folgendes:

Let werden , um eine Faktorisierung von L . Dann ist Y = ⋂ x ∈ X x - 1 L , X = ⋂ y ∈ Y L y - 1 , dh jeder linke Faktor ist ein Schnittpunkt von rechten Quotienten, und jeder rechte Faktor ist ein Schnittpunkt von linken Quotienten. Umgekehrt wird jede Kreuzung von links Quotienten von L ist ein richtiger Faktor L , und jeder Schnittpunkt der rechten Quotienten von L ist ein linker Faktor L .$(X,Y)$$L$

Man beachte, dass es für eine reguläre Sprache nur eine endliche Menge von linken und rechten Quotienten gibt und daher oder ein Problem sich darauf beschränkt, die linken und rechten Quotienten einer Sprache zu berechnen und dann ihren stabilen Abschluss zu berechnen, dh ein Minimum Obermenge der Quotienten, die unter Kreuzung geschlossen wird. Dies sind dann genau die rechten und linken Faktoren, und dann ist es normalerweise leicht zu erkennen, welche Paare Teilmengen von L sind .$\cap$$L$

Beispiel

Um die obigen Punkte zu veranschaulichen, betrachten Sie das erste Beispiel in der Frage (von dem ich auch denke, dass es in der Arbeit falsch ist):

Let . Nun werden die linken Quotienten von L sind die Sätze x - 1 L für x ∈ Σ * , das heißt, diese Worte u in Σ * , die mit dem Präfix werden kann x , dh x u ∈ L . Wann ist y - 1 L = x - 1 L für verschiedene x , y ? Dies ist genau dann der Fall, wenn $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$und kann zu Wörtern in L mit genau den gleichen Suffixen erweitert werden. Dies bedeutet, dass sie, um es bekannter zu machen, Nerode-äquivalent sind und die Suffixe, die zum Anhängen an Wörter in einer Nerode-Klasse benötigt werden, genau die jeweiligen linken Quotienten sind.$y$$L$

Für wir, dass unsere Nerodenäquivalenzklassen sind$L$

• , die Menge der Wörter, die kein b als Faktor enthalten und mit a enden, $N_1$$ab$$a$
• ,der Satz von Worten mitEndung b und nicht enthaltend eine b als Faktor, und $N_2$$b$$ab$
• , die Menge von Wörtern, die a b als Faktor enthalten, dh N 3 = $N_3$$ab$$N_3 = L$

Sie können mit den folgenden Mengen erweitert werden (dh dies sind die linken Quotienten der Wörter in den jeweiligen Klassen):

• für x in N 1 besteht aus allen Wörtern in L (jedes Wort kann mit einem Wort, das a b als Faktor enthält, erweitert werden und wird so zu einem Wort in L ) und b Σ ∗ , das heißt S 1 = L ∪ B Σ $S_1 = x^{-1}L$$x$$N_1$$L$$ab$$L$$b\Sigma^\ast$$S_1 = L \cup b\Sigma^\ast$
• für x in N 2 ist die Sprache selbst, dh S 2 = L und$S_2 = x^{-1}L$$x$$N_2$$S_2 = L$
• für x in N 3 ist offensichtlich Σ * . Das heißt, wir haben drei richtige Faktoren für L gefunden . Da S 2 ⊂ S 1 ⊂ S 3 ist , ist ihr ∩- stabiler Verschluss trivial S 1 , S 2 , S 3 , und das sind dann genau die richtigen Faktoren.$S_3 = x^{-1}L$$x$$N_3$$\Sigma^\ast$$L$$S_2\subset S_1\subset S_3$$\cap$${S_1,S_2,S_3}$

Daher unsere Faktorisierung Satz ist von der Form ( P 1 , S 1 ) , ( P 2 , S 2 ) , ( P 3 , S 3 ) .$\mathcal{F}_L$$(P_1,S_1),(P_2,S_2),(P_3,S_3)$

Nun verwenden wir für die linken Faktoren die Gleichungen des Anfangs dieser Antwort:$P_i$

.

Für ergibt dies L ∪ Σ * ein , für P 2 erhalten wir Σ * und P 3 , erhalten wir L . Sie können dies durch Einsichtnahme (die häufigste Entschuldigung dafür, dass Sie zu faul sind, einen formalen Beweis zu erbringen) oder durch die explizite Berechnung der rechten Quotienten (die der Berechnung der linken Quotienten ziemlich analog, wenn auch nicht vollständig ist) erkennen. Unsere Faktorisierungen sind also gegeben durch F L = u , v , w wo$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)$
• und$v = (P_2, S_2) = (\Sigma^\ast, \Sigma^\ast ab \Sigma^\ast)$
• $w = (P_3, S_3) = (\Sigma^\ast ab \Sigma^\ast, \Sigma^\ast)$

Zusammenfassung

Zusammenfassend (als Sie nach einem einfachen Verfahren fragten):

• Für die Faktorisierung einer Sprache Berechnen , zuerst die linken Quotienten berechnen L .$L$$L$
• Sie können dies in der Sprache der Arbeit tun, indem Sie einen minimalen DFA für L konstruieren und dann für jeden Zustand q in A (der als Nerode-Äquivalenzklasse einem linken Quotienten entspricht) die Zukunft von q in A berechnen Erhalten eines linken Quotienten der Sprache für jeden Zustand.$A$$L$$q$$A$$q$$A$
• Die auf diese Weise erhaltene Sammlung von linken Quotienten ergibt im allgemeinen eine Teilmenge der rechten Faktoren.$S_R$
• Compute then the $\cap$-stable closure of $S_R$, which can be done in practice by forming the intersection of any subset of $S_R$ and adding any subset obtained in this way to $S_R$.
• The set $S_R$ together with all the intersections from the previous step is then the set of right factors of $L$.
• In order to obtain the left factors, we can compute the right quotients of $L$.
• $Ly^{-1}$$y\in \Sigma^\ast$$x\neq y$$Ly^{-1} = Lx^{-1}$$u\in \Sigma^\ast$$ux \in L \Leftrightarrow uy \in L$
• um zu berechnen$Lx^{-1}$$q$ in $A$ such that $x$ is contained in the future of $q$. The union of the pasts of those states constitute one right quotient. Find all these quotients.
• You know you are done when you have found as many left factors as you have right factors.
• Find those pairs of left and right factors $X,Y$ such that $X\cdot Y \subseteq L$. This is $\mathcal{F}_L$.

1. The Universal Automaton by Lombardy and Sakarovitch (in Texts in Logic and Games, Vol 2: Logic and Automata: History and Perspectives, 2007)