CMI2020-B: 5

Question

Let $\Sigma=\{a,b\}.$ For two non-empty languages $L_1$ and $L_2$ over $\Sigma$, we define $Mix(L_1,L_2)$ to be $\{w_1\;u\;w_2\;v\;w_3|\;u\in L_1,v\in L_2,w_1,w_2,w_3\in \Sigma^*\}$.

1. Give two languages $L_1$ and $L_2$ such that $ Mix(L_1,L_2)  \neq Mix(L_2,L_1) $.
2. Show that if $L_1$ and $L_2$ are regular, the language $Mix(L_1,L_2)$ is also regular.
3. Provide languages $L_1$ and $L_2$ that are not regular, for which $Mix(L_1,L_2)$ is regular.

Answer 1