[Solved]: Proving regular languages are closed under a form of interleaving

Problem Detail: 

I've got the following definitions:

$$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$

when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means the $i$-th letter in $w$.

$$\mathrm{Interleave}\,(L_1,L_2)\ \ = \!\!\!\!\bigcup_{\substack{x\in L_1,\ y\in L_2,\\ |x|=|y|}}\!\!\!\! \mathrm{Interleave}\,(x,y)$$ when both $L_1$ and $L_2$ are languages.

I have to prove that if I know that $L_1$ and $L_2$ are both regular languages, $\mathrm{Interleave}\,(L_1,L_2)$ is a regular language as well.

I have absolutely no idea how to do it .

Thanks in advance.

Asked By : OrWn

Answered By : David Richerby

Hint. Because $L_1$ and $L_2$ are both regular, you know they're accepted by NFAs (or DFAs; it doesn't matter) $M_1$ and $M_2$, respectively. To show that $\mathrm{Interleave}\,(L_1,L_2)$ is regular, show that it's accepted by some NFA $M$. For each character it receives, $M$ can decide to act either like $M_1$ or like $M_2$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42347