Problem Detail: I’ve got the following definitions: $$mathrm{Interleave},(x,y) = {w_1dots w_nmid w_iin{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{xin L_1, yin 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
