Problem Detail: Let $L_1, L_2$, two regular languages and the operations: $$Mix_1(L_1, L_2) ={ a_1b_1a_2b_2ldots a_nb_n | nge 0 land a_1,a_2,ldots ,a_n,b_1,b_2,ldots ,b_ninSigma land a_1a_2ldots a_nin L_1 , b_1b_2ldots b_nin L_2}$$ $$Mix_2(L_1, L_2) = { x_1y_1x_2y_2ldots x_ny_n | nge 0 land x_1,x_2,ldots,x_n,y_1,y_2,ldots,y_ninSigma^* , x_1x_2ldots x_nin L_1 land y_1y_2ldots y_nin L_2}$$
Prove that regular languages are closed under $Mix_1$ and $Mix_2$ operations.
So for the first operation:
Let $D_1, D_2$, two DFA’s accepting $L_1, L_2$, respectively. We define $D = (Q,Sigma, delta, q_0, F)$. Where $Q = Q_1 cup Q_2$. The transition function, $delta$ will behave as $delta_1$ and $delta_2$. But in addition, Let’s define $n = left|Sigmaright|$, then we make $n$ transitions from every $q_iin Q_1$ to $q_jin Q_2$ (and vice versa) for every $sigma in Sigma$. So it’s pretty easy to see that $D$ accepts $Mix_1(L_1, L_2)$. Question:
How can I show that regular languages are closed under $Mix_2$?
Asked By : Elimination
Answered By : Hendrik Jan
Take any string over the alphabet $Sigma$. Colour some of the letters red and the remaining letters green. Accept the original string if the red letters form a string in $L_1$ and the green ones are in $L_2$. More technically, regular languages are closed onder intersection and under (inverse) homomorpisms. Let $Gamma = Sigma times {1,2}$ be an alphabet with colours. Define the homomorphisms $h_i:Gamma^* toSigma^*$, $i=1,2$ by $h_i(a,i) = a$ and $h_i(a,j) = varepsilon$ for $ineq j$. These keep only letters of their assigned colour, whereas their inverses colour the letters into that asigned colour while inserting arbitrary letters of the other colour. Finally let $g:Gamma^* toSigma^*$ be the morphism $g(a,i) = a$ (which removes the colour). Then $Mix_2(L_1,L_2) = g(; h_1^{-1}(L_1) cap h_2^{-1}(L_2) ;)$. PS. Let $R_{12}$ be the regular language $[(Sigmatimes {1})(Sigmatimes {2})]^*$. Then $Mix_1(L_1,L_2) = g(; h_1^{-1}(L_1) cap h_2^{-1}(L_2) cap R_{12} ;)$. Just for fun, $L_1 cdot L_2 = g(; h_1^{-1}(L_1) cap h_2^{-1}(L_2) cap (Sigmatimes {1})^*(Sigmatimes {2})^* ;)$. Regular languages are closed under concatenation 🙂
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42751
