Exercise 16 (Homework 2).
(regular languages,
intercalAND)
IntercalAND of regulars is regular
Given two languages L_1, L_2 \subseteq \Sigma^*, define
\mathtt{intercalAND}(L_1,L_2) = \{x_1y_1 ... x_ny_n \mid (n \geq 1) \, \wedge \, (x_1, \dots , x_n ,y_1, \dots ,y_n \in \Sigma) \, \wedge \, (x_1\cdots x_n \in L_1) \, \wedge \, (y_1 \cdots y_n \in L_2)\}.
Show that if L_1 and L_2 are regular, then \mathtt{intercalAND}(L_1,L_2) is also regular.