# Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties?

Let $$L$$ be a regular language over alphabet $$\Sigma$$. $$L$$ is the result of merging $$2$$ languages letter by letter that is for $$a_1a_2...a_n\in L_1, b_1b_2...b_n\in L_2, L=a_1b_1a_2b_2...a_nb_n$$. $$\epsilon \in L \iff\epsilon \in L_1,L_2$$. Does this mean that $$L_1$$ is necessarily regular?

At first I tried to prove that this is true using closure properties of regular languages before finding out that the claim is not true (e.g. $$L_1=\{a^ib^i|i\ge 0\}, L_2=\{ab\}$$).

I'd like to understand though what's wrong with my proof:

1) Define homomorphism $$h:\Sigma\to \Sigma^*\cup \Sigma'^*$$ as follows: $$h(\sigma)=h(\sigma')=\sigma$$ for $$\sigma,\sigma'\in \Sigma.$$

2) Let $$X=h^{-1}(L)\cap(\Sigma\Sigma^*)$$

3) Define another homomorphism: $$f_1:\Sigma^*\cup \Sigma'^*\to \Sigma$$ like this: $$f_1(\sigma)=\sigma\\f_1(\sigma')=\epsilon$$ 4) Define another homomorphism: $$f_2:\Sigma^*\cup \Sigma'^*\to \Sigma$$ like this: $$f_2(\sigma')=\sigma'\\f_2(\sigma)=\epsilon$$ Then $$L_1=f_1(X), L_2=f_2(X)$$. Now if either $$L_1$$ or $$L_2$$ is not regular than it's contradiction because by closure properties they should've been regular. Where is my mistake?

EDIT: following one of the comments, the problem with the attempt to use closure properties is that apply the homomorphisms $$f_1,f_2$$ on $$X$$ we may get a different language from the original one.

• You have a counterexample in your question. What do you learn when you apply this counterexample in the construction of your suggested proof? – Hendrik Jan Jan 29 at 14:42
• Now I see, if I apply my construction I get a different language. – Yos Jan 29 at 14:56
• @Yos, write an answer? – Apass.Jack Jan 29 at 18:51
• @Apass.Jack I added an edit section in the OP, the answer seems to be so minimal that I don't think it warrants an answer. Let me know if the rules encourage adding an official answer in such situations. – Yos Jan 29 at 18:56
• For this kind of exercises it is often useful to check for trivial cases, first. E.g. one might assume the conjecture, choose (say) $L_1$ to be the empty (or full) language, and simplify the statement accordingly. Sometimes, a counterexample can now be seen. – chi Jan 30 at 11:28

Your construction outputs the language $$\{ w \in L_1 : \exists z \in L_2 \text{ s.t. } |z|=|w| \}.$$ In words, it outputs those words in $$L_1$$ whose length matches the length of some word in $$L_2$$. In general, this could be much smaller than $$L_1$$.
In particular, if $$L_2$$ is a finite language, then the result of merging $$L_1$$ and $$L_2$$ is finite, and so regular, for every language $$L_1$$.