Particionar un lenguaje regular infinito en 2 idiomas regulares infinitos disjuntos

Dado cualquier lenguaje regular infinito , ¿cómo puedo probar que puede dividirse en 2 idiomas regulares infinitos disjuntos ? Esto es: , , y y son ambos tanto infinito y regular.$L$$L$$L_1, L_2$$L_1 \cup L_2 = L$$L_1 \cap L_2 = \varnothing$$L_1$$L_2$

Hasta ahora, pensé en:

1. usando el lema de bombeo de manera que pero no pudo probar que están dichoint o que cubren completamente.

   $$\begin{gather} L_1 &= \{ xy^nz \mid \text{\(n\) is even} \} \\ L_2 &= \{ xy^mz \mid \text{\(m\) is odd} \} \\ \end{gather}$$ $L$

2. Usando las particiones de lenguaje regular en dichas clases de equivalencia, pero no he descubierto cómo determinar si una clase de equivalencia es regular o infinita.$\Sigma^*$

Deje . El teorema de Parikh muestra que es un conjunto eventualmente periódico. Deje que el período final sea . Como es infinito, hay algún desplazamiento tal que para todo . Por lo tanto, el lenguaje es infinito (contiene todas las palabras de longitud para algunos ), y el lenguaje también es infinito (contiene todo palabras de longitud para algunos$S = \{ |w| : w \in L \}$$S$$\ell$$L$$a$$a + k\ell \in S$$k \geq 0$$L_1 = \{ w \in L : |w| \equiv a \pmod{2\ell} \}$$a + 2k\ell$$k \geq 0$$L_2 = L \setminus L_1$$a + (2k+1)\ell$$k \geq 0$, así como posiblemente otras palabras). Te dejaré mostrar que son ambos regulares.$L_1,L_2$

Cada lenguaje normal es aceptado por algunos DFA mínimos. Para un lenguaje regular infinito , llamemos a tal DFA . Considere cualquier estado que se pueden visitar más de una vez durante el procesamiento de un trozo de cuerda en . Si se puede visitar más de una vez, se deduce que se puede visitar cualquier número de veces. Definir y Este es un DFA, por lo que solo hay un camino. Cualquier cadena en$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}\}$$ $L$es aceptado por el DFA y debe visitar el estado varias veces (tal vez cero). El estado puede ser visitado un número ilimitado de veces; por lo tanto, sabemos que hay infinitas cadenas en (ya que hay palabras que hacen que el estado se visite 1 vez, 3 veces, etc.) y que hay infinitas cadenas en (ya que hay palabras que causan estado para ser visitado 0 veces, 2 veces, etc.). Cualquier cadena dada es o bien en o , y no puede estar en ambos, por lo . Sin embargo, cualquier palabra en está garantizado a estar en uno de estos dos conjuntos, por lo .$L_1$$L_0$$L_1$$L_0$$L_0 \cap L_1 = \emptyset$$L$$L_0 \cup L_1 = L$