Exercici 16 (Tasca 2).
(regular languages,
intercalAND)
L’IntercalAND de regulars és regular
Donats dos llenguatges L_1, L_2 \subseteq \Sigma^*, definim
\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)\}.
Demostreu que si L_1 i L_2 són regulars, aleshores \mathtt{intercalAND}(L_1,L_2) també és regular.