Building an automaton that defines a language

Question

I have $2$ languages, $L_1$ and $L_2$, both are part of $L$-dfa. I have the following language:

$$L_0= \{a_1\cdot b_1\cdot a_2\cdot b_2\cdot\ldots a_n\cdot b_n \mid a_i,b_i\in\Sigma, a_1,a_2,\ldots,a_n\in L_1, b_1,b_2,\ldots,b_n\in L_2\}$$

I need to build an automaton for $L_0$ so I can prove it is also a part of $L$-dfa.

My first hunch was to draw one, and try to work the drawing into an expression, but i'm running into trouble trying to draw it. Is there a good way to tackle such a question? If it was a simple automata, a drawing would be all I need to see the expression, but with something more complex as this, I am truly lost..

Answer 1

If I understand the question correctly, you can use a two state DFA:

Start------->Z for any $a_i \in L_1$

Z------->Start for any $b_i \in L_2$

Accept at the start state.

Answer 2

In fact, the language remains regular even if they are strings - consider the regular expression $(L_1 \cdot L_2)^{*}$.

Let $M_1$ be an NFA for $L_1$ and $M_2$ an NFA for $L_2$. Such that both have a single accepting state, $q_1$ and $q_2$ respectively - such machines always exist. We will denote their start states $s_1$ and $s_2$.

If we add an $\varepsilon$ transition from $s_1$ to $q_2$, and from $q_1$ to $s_2$, and make only $s_1$ an accepting state the resulting machine will only accept strings from the regex $(L_1 \cdot L_2)^{*}$.

To give a brief sketch of the proof, which you should write in full if this is homework, we know that for each $a_i \in L_1$ there is a path from $s_1$ to $q_1$, and for any $b_i \in L_2$ there is a path from $s_2$ to $q_2$. We can always make the empty transitions from $s_1$ to $q_1$ and $s_2$ to $q_2$, so for any language consisting of a sequence of $a_ib_i$ we can find a path from $s_1$ to $s_1$ by joining all these paths together. The DFA can then be constructed by converting this NFA back.