Unterschied zwischen den Sprachen, die von zwei DFAs mit unterschiedlichen Ausgangszuständen / Akzeptanzzuständen akzeptiert werden?

Kürzlich habe ich eine Frage zu Math SE gestellt. Noch keine Antwort. Diese Frage bezieht sich auf diese Frage, aber mehr technische Details zur Informatik.

Gegeben sind zwei DFAs $A = (Q, \Sigma, \delta, q_1, F_1)$ und $B = (Q, \Sigma, \delta, q_2, F_2)$ wobei die Menge der Zustände, das Eingabealphabet und die Übergangsfunktion von $A$ und $B$ sind gleich, die Anfangszustände und die Endzustände (Akzeptanzzustände) können unterschiedlich sein. Sei $L_1$ und $L_2$ die von $A$ und akzeptierte Sprache$B$ , respectively.

Es gibt vier Fälle:

1. und F 1 = F 2 .$q_1 = q_2$$F_1 = F_2$
2. und F 1 = F 2 .$q_1 \neq q_2$$F_1 = F_2$
3. und F 1 ≠ F 2 .$q_1 = q_2$$F_1 \neq F_2$
4. und F 1 ≠ F 2 .$q_1 \neq q_2$$F_1 \neq F_2$

Meine Frage ist

Was sind die Unterschiede zwischen und L 2 in den Fällen 2, 3 und 4?$L_1$$L_2$

Ich habe eine spezifischere Frage in dieser Richtung,

Das Übergangsmonoid eines Automaten ist die Menge aller Funktionen auf der Menge von Zuständen, die durch Eingabezeichenfolgen induziert werden. Weitere Informationen finden Sie auf der Seite . Das Übergangsmonoid kann als ein Monoid angesehen werden, das auf die Menge von Zuständen einwirkt. Weitere Informationen finden Sie auf dieser Wiki-Seite .

In vielen Literaturen wird ein Automat als stark verbunden bezeichnet, wenn die Monoidwirkung transitiv ist, dh es gibt immer mindestens einen Übergang (Eingabezeichenfolge) von einem Zustand in einen anderen Zustand.

Wenn und B stark verbundene Automaten sind, was sind die Unterschiede zwischen L 1 und L 2 in den obigen Fällen 2, 3 und 4?$A$$B$$L_1$$L_2$

Gibt es Literaturen, die diese Themen ausführlich diskutieren?

Ich habe viele Bücher und Artikel durchsucht und bisher nichts hilfreiches gefunden. Ich glaube, ich habe noch nicht die passenden Schlüsselwörter. Deshalb suche ich Hilfe. Alle Hinweise / Referenzen werden sehr geschätzt.

Da stark verbunden sind, existieren, wenn q 1 ≠ q 2 ist , Wörter p 1 , p 2, so dass δ ( q 1 , p 1 ) = q 2 und δ ( q 2 , p 2 ) = q 1 .$A,B$$q_1\neq q_2$$p_1,p_2$$\delta(q_1,p_1)=q_2$$\delta(q_2,p_2)=q_1$

Betrachten Sie Fall 2, dann wenn p 2 w ∈ L ( B ) ist , und x ∈ L ( B ), wenn p 1 x ∈ L ( A ) . Sie können also ein Präfix hinzufügen, um zwischen den Sprachen zu wechseln.$w\in L(A)$$p_2w\in L(B)$$x\in L(B)$$p_1 x\in L(A)$

Betrachten Sie dann noch einmal Fall 3 - durch starke Konnektivität dort höchstens Wörter s 1 , . . . , s k so, dass Sie für jedes q i ∈ F 1 das δ ( q i , s i ) ∈ F 2 haben , und ähnlich für die andere Richtung (von B nach A ).$|F_1|$$s_1,...,s_k$$q_i\in F_1$$\delta(q_i,s_i)\in F_2$$B$$A$

So können Sie Suffixe erstellen, um zwischen Sprachen zu wechseln.

Wenn Sie diese kombinieren, können Sie die Unterschiede mithilfe von Präfixen und Suffixen charakterisieren. Zum Beispiel ist in Fall 4 wenn p 1 w s i in L ( A ) für einige s i in einer vorbestimmten endlichen Menge ist.$w\in L(B)$$p_1 w s_i$$L(A)$$s_i$

Tatsächlich können Sie zu diesen Wörtern sogar etwas Interessantes sagen: Definieren Sie als DFA, wobei q 1 der Anfangszustand und q 2 der Endzustand ist. In Fall 2 haben Sie L ( B ) = L ( C ) ⋅ L ( A ) (und ähnlich für die andere Richtung).$C$$q_1$$q_2$$L(B)=L(C)\cdot L(A)$

Was die Suffixe betrifft, sind die Dinge komplizierter, da Sie nicht vorbestimmen können, in welchem ​​Endzustand Sie enden werden. Ich bin nicht sicher, ob Sie dies als Verkettung schreiben können, aber Sie können schreiben, wobei A q der DFA ist, der aus A erhalten wird , indem F gesetzt wird = { q } und E q ist ein DFA, der in q mit den Endzuständen F 2 beginnt .$L(B)=\bigcup_{q\in F_1}L(A_q)\cdot L(E_q)$$A_q$$A$$F=\{q\}$$E_q$$q$$F_2$

Für Fall 4 können Sie beide kombinieren.

Möglicherweise befürchten Sie, dass dies keine echte Antwort ist, sondern lediglich eine Charakterisierung von Eigenschaften mithilfe von Wörtern anstelle von Zuständen. Dies ist jedoch eine typische Antwort auf diesem Gebiet (ähnlich dem Myhill-Nerode-Theorem).