2
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\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$ Jan 29, 2019 at 14:42
  • $\begingroup$ Now I see, if I apply my construction I get a different language. $\endgroup$
    – Yos
    Jan 29, 2019 at 14:56
  • $\begingroup$ @Yos, write an answer? $\endgroup$
    – John L.
    Jan 29, 2019 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, 2019 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, 2019 at 11:28

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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