¿Se cierran las lenguas regulares con una operación de barrido completo?

Question

Sean dos lenguas $L_1,L_2$ definimos la operación full-shuffle como $S(L_1,L_2)=\{w \mid w=w_1w_2...w_k\}$ tal que $w_1,w_3,...\in L_1$ y $w_2,w_4...\in L_2$ . En otras palabras, el lenguaje $L$ sólo contiene palabras que podemos construir a partir de una palabra $L_1$ seguido de una palabra de $L_2$ , seguido de una palabra de $L_1$ , seguido de una palabra de $L_2$ y así sucesivamente...

¿Cómo puedo demostrar que las lenguas regulares se cierran con esta operación?

Tengo algunas dificultades para imaginar los autómatas formalizados que resultan de esto.

Hice lo siguiente desde p49, en Introducción a la teoría de la computación de A. Meheshwari y M. Smid .

Dejemos que $M_1=(Q_1,\Sigma,\delta_1,q_1,F_1)$ sea un NFA tal que $A_1=L(M_1)$ y $M_2=(Q_2,\Sigma,\delta_2,q_2,F_2)$ sea un NFA tal que $A_2=L(M_2)$ . Construiremos un NFA $M=(Q,\Sigma,\delta,q_0,F)$ tal que $L(M)=A_1A_2A_1A_2A_1...$

1. $Q = Q_1 \cup Q_2$ ( $\cup Q_1 \cup Q_2...?$ pero sigue siendo lo mismo, ¿no?)
2. $q_0=q_1$
3. $F=F_1 \cap F_2$ por lo que tenemos que tener palabras de ambos $L_1$ y $L_2$ .
4. $\delta : Q\times\Sigma_\epsilon \rightarrow P(Q)$ se define como sigue :

$$\delta(r,a)=\begin{cases} \delta_1(r,a)\mbox{ if $r\in Q_1$}\\ \delta_2(r,a)\mbox{ if $r\in Q_2$}\\ \end{cases}$$

Soy nuevo en este tipo de pruebas y no estoy seguro de ello.

Answer 1

Sólo hay que utilizar expresiones regulares en lugar de autómatas. De hecho, $$S(L_1,L_2) = (L_1L_2)^* \cup (L_1L_2)^*L_1$$

Answer 2

Pues bien, te faltan las partes cruciales. En primer lugar, el conjunto de estados de aceptación debe ser $F_1 \cup F_2$ , no la intersección. La idea es que empecemos en $M_1$ y cuando hemos aceptado una palabra $w_1$ en $M_1$ entonces elegimos de forma no determinista entre detenernos ahí, o continuar leyendo una palabra $w_2$ que debería estar en $M_2$ . Por lo tanto, debe añadir transiciones $$\delta(r,a) = \begin{cases} \delta_2(r,a) \cup \{q_1\} \text{ if } r \in F_2 \text{ and } a = \varepsilon \\ \delta_1(r,a) \cup \{q_2\} \text{ if } r \in F_1 \text{ and } a = \varepsilon\end{cases}$$ que puede llevarle de un estado de aceptación en uno de los autómatas al estado de inicio en el otro. De esta manera, se puede "barajar" de un lado a otro entre $M_1$ y $M_2$ .