1

I have 3 languages L1, L2 and L3 with

x$\in$L1, y$\in$L2, z$\in$L3 ;

x=$a_{1}a_{2}a_{3}...a_{n}$,
y=$b_{1}b_{2}b_{3}...b_{n}$ and
c=$a_{1}b_{1}a_{2}b_{2}a_{3}b_{3}...a_{n}b_{n}$.

Words of L3 are alternating combinations of x an y , if x and y are of the same size |a|=|b|. How can I prove, that L1 and L2 being regular languages, L3 is also regular?

I guess, one could construct a NFA . Starting point is in L1. After"reading" a symbol, there is an epsilon transition to starting point of L2. Reading, epsilon transition to second node of L1 and so on. If there is an existing NFA of L3, than L3 is regular. But just by saying you could do something like that, is no proof at all. Is there a better way?

with best regards

letter
  • 43

2 Answers2

1

One can give a short proof using the closure properties of regular languages.

Let $A$ be the alphabet and let $p, p_1, p_2: A \times A \to A^*$ be the maps defined by $p(a,b) = ab$, $p_1(a,b) = a$ and $p_2(a,b) = b$. These maps extend to monoid homomorphisms from $(A \times A)^*$ to $A^*$. Now $L_3 = p(p_1^{-1}(L_1) \cap p_2^{-1}(L_2))$ and since regular languages are closed under intersection, homomorphisms and inverse homomorphisms, $L_3$ is regular.

J.-E. Pin
  • 40,163
0

The automata sound messy but the Myhill-Nerode Theorem will do it.

Suppose that $L_1$ is regular. By MNT, there are only finitely many different sets (called "tails") $$T_{L_1}(x)=\{w\in\Sigma^*\mid xw\in L_1\}\ .$$ Likewise for $L_2$. Now consider $L_3$. If $x$ is any word in $\Sigma^*$ and $x=x_1\cdots x_m$ has even length, then $$\eqalign{T_{L_3}(x) &=\{w\in\Sigma^*\mid xw\in L_3\}\cr &=\{w_1\cdots w_n\mid \hbox{$n$ is even},\ w_1w_3\cdots\in T_{L_1}(x_1x_3\cdots),\ w_2w_4\cdots\in T_{L_2}(x_2x_4\cdots)\}\ .\cr}$$ Now there are only finitely many options for each of the two tails on the RHS, and each pair gives exactly one tail on the LHS. So we only get finitely many tails in $L_3$. Repeat if $x$ has odd length, the tails look slightly different (give it a try) but there are still only finitely many. So $L_3$ has only finitely many tails altogether and $L_3$ is regular.

Note that this is where MNT beats the Pumping Lemma: it is an if and only if theorem.

David
  • 82,662