How can I prove this language is regular using just closures and homomorphism? $$ L = \{a_1b_1a_2b_2\dotsm a_nb_n \mid a_i \in L_1 , b_i \in L_2\} $$ and we know $L_1$ and $L_2$ are regular.

  • $\begingroup$ How is $n$ defined? $\endgroup$
    – adrianN
    Jan 5, 2017 at 14:24
  • $\begingroup$ n is a finite number $\endgroup$
    – user64211
    Jan 5, 2017 at 14:40
  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Also, I suspect what adrianN is asking is: Is $n$ fixed in advance (and the same for every word in $L$), or is it free to vary? $\endgroup$
    – D.W.
    Jan 5, 2017 at 19:07
  • $\begingroup$ I'm trying to understand what are the steps i am supposed to do in order to solve this kind of questions. I don't know how to begin and would love to get some help. $\endgroup$
    – user64211
    Jan 6, 2017 at 6:28
  • $\begingroup$ Try to express $L$ in terms of $L_1$ and $L_2$ using some known algebraic operator. E.g. If we knew that (random example) $L = (L_1(L_1 + L_2)) \setminus L_2L_1$ we could conclude $L$ regular by the closure properties. $\endgroup$
    – chi
    Jan 6, 2017 at 10:53

1 Answer 1


To get you started, consider a restricted version of your languge: $$ L'=\{ab\mid a\in L_1, b\in L_2\} $$ Notice that $L$ is the concatenation $L'=L_1\circ L_2$. Can you carry on from there?


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.