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.

  • 1
    $\begingroup$ You have a counterexample in your question. What do you learn when you apply this counterexample in the construction of your suggested proof? $\endgroup$ – Hendrik Jan Jan 29 at 14:42
  • $\begingroup$ Now I see, if I apply my construction I get a different language. $\endgroup$ – Yos Jan 29 at 14:56
  • $\begingroup$ @Yos, write an answer? $\endgroup$ – Apass.Jack Jan 29 at 18:51
  • $\begingroup$ @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. $\endgroup$ – Yos Jan 29 at 18:56
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.