Unterteilen Sie eine unendliche reguläre Sprache in zwei disjunkte unendliche reguläre Sprachen

Wie kann ich bei einer unendlichen regulären Sprache $L$ beweisen, dass $L$ in zwei disjunkte unendliche reguläre Sprachen $L_1, L_2$ ? Das heißt: $L_1 \cup L_2 = L$ , $L_1 \cap L_2 = \varnothing$ und und$L_1$$L_2$ sind beide unendlich und regelmäßig.

Bisher dachte ich an:

1. unter Verwendung des Pump-Lemmas, so dass

   $$\begin{gather} L_1 &= \{ xy^nz \mid \text{\(n\) is even} \} \\ L_2 &= \{ xy^mz \mid \text{\(m\) is odd} \} \\ \end{gather}$$ , konnte aber nicht beweisen, dass sie dijunkt sind oder$L$vollständigbedecken.

2. Mit den regulären Sprach Partitionen $\Sigma^*$ in dijoint Äquivalenzklassen, aber ich habe nicht herausgefunden, wie zu bestimmen , ob eine Äquivalenzklasse regelmäßig oder unendlich ist.

Sei . Der Satz von Parikh zeigt, dass S eine eventuell periodische Menge ist. Die eventuelle Periode sei ℓ . Da L unendlich ist, gibt es einen Versatz a, so dass a + k ℓ ∈ S für alle k ≥ 0 ist . Somit ist die Sprache ist unendlich (es enthält alle Wörter der Länge für einige$S = \{ |w| : w \in L \}$$S$$\ell$$L$$a$$a + k\ell \in S$$k \geq 0$a + 2 k ℓ k ≥ 0 L 2 = L ∖ L 1 a + ( 2 k + 1 ) ℓ k ≥ 0 L 1 , L $L_1 = \{ w \in L : |w| \equiv a \pmod{2\ell} \}$$a + 2k\ell$$k \geq 0$), und die Sprache ist ebenfalls unendlich (sie enthält alle Wörter der Länge für einige sowie möglicherweise andere Wörter). Ich werde Sie zeigen lassen, dass beide regulär sind.$L_2 = L \setminus L_1$$a + (2k+1)\ell$$k \geq 0$$L_1,L_2$

Jede reguläre Sprache wird von einem minimalen DFA akzeptiert. Für eine unendliche reguläre Sprache , nennen wir eine solche DFA M L . Betrachten Sie jeden Zustand q, der mehr als einmal besucht werden kann, während eine Zeichenfolge in L verarbeitet wird . Wenn q mehr als einmal besucht werden kann, kann es beliebig oft besucht werden. Definiere L 1 = { w ∈ L ∣ q  wird ungerade oft besucht } und L 0 = { w ∈ L ∣ q  wird gerade oft besucht $L$$M_L$$q$$L$$q$

$$L_1 = \{w \in L \mid q\text{ is visited an odd number of times}\}$$ $$L_0 = \{w \in L \mid q\text{ is visited an even number of times}\}$$ Dies ist ein DFA, es gibt also nur einen Pfad. Jede Zeichenfolge in wird vom DFA akzeptiert und muss den Status einige Male besuchen (möglicherweise Null). Der Staat kann unbegrenzt oft besucht werden; Daher wissen wir, dass es in L 1 unendlich viele Zeichenfolgen gibt (da es Wörter gibt, die bewirken, dass der Zustand 1 Mal, 3 Mal usw. besucht wird) und dass es in L 0 unendlich viele Zeichenfolgen gibt (da es Wörter gibt, die veranlassen, dass der Zustand 0 Mal, 2 Mal usw. besucht wird). Jede gegebene Zeichenkette ist entweder in L 1 oder L 0 und kann nicht in beiden sein, also ist L 0 ∩ L 1 = $L$$L_1$$L_0$$L_1$$L_0$$L_0 \cap L_1 = \emptyset$. Es ist jedoch garantiert, dass sich jedes Wort in in einer dieser beiden Mengen befindet, sodass L 0 ∪ L 1 = L ist .$L$$L_0 \cup L_1 = L$