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

  • $\begingroup$ Are the $a_i$ strings in your language or characters in the alphabet or both? $\endgroup$ – Vladhagen Nov 18 '13 at 20:30
  • 1
    $\begingroup$ If they are strings, it would seem that maybe Pumping Lemma shows the language is not regular. I would need to think about that a bit, but it seems that that would be so. $\endgroup$ – Vladhagen Nov 18 '13 at 20:33

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.

  • $\begingroup$ This assumes that your strings in $L_0$ are comprised of alternating LETTERS in the alphabets. $\endgroup$ – Vladhagen Nov 18 '13 at 20:58

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.


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.