4
$\begingroup$

Given a language: $L = \{\; a_1b_1a_2b_2a_3b_3\dots a_nb_n \mid \forall i: a_i,b_i \in \Sigma, a_1\dots a_n \in L_1\ , b_1\dots b_n \in L_2 \;\}$

Also $L_1, L_2$ are regular languages.

Using closure only (homomorphism) prove that L is also regular language.


I think there can be a mapping $h\colon (L_1 \cup L_2) \to \Sigma$, then use $h^{-1}(\Sigma)$ in order to show regularity. I'm a bit stuck over here.

$\endgroup$
  • $\begingroup$ A homomorphism is a mapping from an alphabet to strings, not from a language to an alphabet. $\endgroup$ – Yuval Filmus Jan 8 '17 at 20:11
  • 1
    $\begingroup$ 1. Is $n$ fixed in advance? Or is it allowed to vary? 2. What does your notation mean? Do you mean that every word in $L$ is of length exactly $2$? Or is it length $2n$? $\endgroup$ – D.W. Jan 8 '17 at 20:55
2
$\begingroup$

The idea is to create two copies of the alphabet $\Sigma$, say $\Sigma_1,\Sigma_2$; each $\sigma \in \Sigma$ corresponds to $\sigma^{(i)} \in \Sigma_i$. You now show that the following languages are regular: $$ \begin{align*} \tilde{L}_1 &= \{a_1^{(1)}b_1^{(2)}\ldots a_n^{(1)}b_n^{(2)} : a_1 \ldots a_n \in L_1 \}, \\ \tilde{L}_2 &= \{a_1^{(1)}b_1^{(2)}\ldots a_n^{(1)}b_n^{(2)} : b_1 \ldots b_n \in L_2 \}, \end{align*} $$ where in both cases only some of the letters are constrained. Now take $\tilde{L}_1 \cap \tilde{L}_2$ and transform it to $L$.

I leave the rest of the details for you to complete.

$\endgroup$
  • $\begingroup$ I thought of another solution, not sure if its also correct. I can probably have a mapping $h: \Sigma_1 \to \Sigma_1 \cup \Sigma_2$ such that $\forall i, h(a_i) = a_ib_i$ then given that $L_1$ is regular i can use homomorphism to prove $L$ regularity. $\endgroup$ – Joey Kaller Jan 8 '17 at 20:28
  • $\begingroup$ There could be more than one solution. Unfortunately we don't verify solutions here. $\endgroup$ – Yuval Filmus Jan 8 '17 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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