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

Improve this question
$\endgroup$
2
  • $\begingroup$ A homomorphism is a mapping from an alphabet to strings, not from a language to an alphabet. $\endgroup$
    – Yuval Filmus
    Commented Jan 8, 2017 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. ♦
    Commented Jan 8, 2017 at 20:55

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jan 8, 2017 at 20:28
  • $\begingroup$ There could be more than one solution. Unfortunately we don't verify solutions here. $\endgroup$
    – Yuval Filmus
    Commented Jan 8, 2017 at 20:34

Your Answer

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

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