# How to construct a DFA for this?

Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of all strings $w$ of the form $w = a_1b_1a_2b_2....a_kb_k$, for $k > 0$, with $a_1a_2 ··· a_k \in A$ and $b_1b_2 ··· b_k \in B$. Show that if A and B are regular then so is $C = shuffle(A, B).$

• Welcome to Computer Science! What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? Aug 15 '14 at 16:58
• Ok, this is not at all a homework problem. I was trying to make connection with construction of concatenation property og regular languages. I was thinking of doing something like defining new states as $Q_1 \times Q_2$ and new transition function $f((x,y),a)=(f_1(x,a),y)\cup (x,f_2(y,a))$. but i don't think its working Aug 15 '14 at 17:05
• Hmm, this k > 0 condition is quite crucial here. Aug 15 '14 at 18:45
• @JamesYang I've added an answer that I think correctly interprets your problem and which approaches things like you're trying to: by constructing an automaton. Notice the definition $\delta''$ of the transition function, although the definition of $Q''$ might be even more instructive. Aug 15 '14 at 18:56
• I second @ZeroUltimax's comment. This seems like pretty basic problem; just dumping the it here is not the most nice thing to do. It makes you look as if you are not ready to spend anytime yourself before asking others to do so. One note about terminology: the term "shuffle" is typically associated with a different operation.
– Raphael
Aug 15 '14 at 21:56

## 1 Answer

Suppose $A$ and $B$ are regular. Let $M_A$ and $M_B$ be DFAs for $A$ and $B$, respectively. We know $M_A$ and $M_B$ exists since every regular language is accepted by some $DFA$.

Let $M_A = (\Sigma, Q, q_0, A, \delta)$ and $M_B = (\Sigma', Q', q_0', A', \delta')$.

We define $M_C = (\Sigma'', Q'', q_0'', A'', \delta'')$ such that $L(M_C) = shuffle(A,B)$.

First, let $\Sigma'' = \Sigma \cup \Sigma'$.

Next, choose $Q'' = \{0, 1\} \times Q \times Q'$.

Now, choose $A'' = \{(0, q, q') \mid q \in A, q' \in A' \}$.

Let $q_0'' = (0, q_0, q_0')$.

Now the fun part: what is the transition function? Here's what it's going to do:

1. If $q'' = (0, q, q')$, then $\delta''(\sigma, q'') = (1, \delta(\sigma, q), q')$ if $\delta(\sigma, q)$ is defined, or undefined otherwise (we're going to get an NFA, but that's OK).

2. If $q'' = (1, q, q')$, then $\delta''(\sigma, q'') = (0, q, \delta'(\sigma, q'))$ if $\delta'(\sigma, q')$ is defined, or undefined otherwise (again, we're going to get an NFA, but that's good enough for establishing regularity).

Basically, we're using the state to encode whether the last symbol we saw was from a word in $A$ or from a word in $B$. We can only accept if the last symbol we saw was from a word in $B$, hence our set of accepting states requiring that we have 0 for the parity. Furthermore, we can only accept if we've seen a complete word from both $A$ and $B$, which is why we require the other components to be accepting states in their respective automata.

You can think of this as two simultaneous DFAs produced from the Cartesian-Product construction for the intersection of the languages. After evaluating each step, we jump to the other machine. The first machine accepts input corresponding to the language $A$, and the second machine accepts input corresponding to the language $B$.

The full proof that this construction yields a correct automaton is left as an exercise.

Note that this construction technically allows $k = 0$, which is not allowed by the language in the question. To complete the exercise, argue that the NFA obtained above can be converted to a DFA by a standard construction, and that intersecting the resulting DFA with a DFA for the language of positive-length strings gives a DFA for the desired language.

• Wait, I can't understand why its working. Its working if $a_i,b_i$'s were given as symbols (path is going like a alternating sequence). If not then dunno why can;t be convinced Aug 15 '14 at 20:08
• like I;m saying let $a_1=f_1f_2$. Starting from initial state after reading $f_1$ it'll go to $(1,q_1,q_0')$ but then after reading $f_2$ where will it go ? $f_2$ doesn't have access on $q_0'$ Aug 15 '14 at 20:16
• Well, I think this should work. First remove those $\{0,1\}$. Now define start state as $(q_1,q_2,0)$ but define other states as $(a,b)|a\in Q_1,b\in Q_2$ and accepting state $F_1 \times F_2$. Now define $\delta$ for non starting states as follows $\delta((a,b),x)=(\delta_1(a,x),b)\cup (a,\delta_2(b,x)$. Now for starting state define it, $\delta((q_1,q_2,0),x)=(\delta_1(q_1,x),q_2)$ .. this'll prove any $a_1b_1.....a_kb_k$ will be accepted but not any of $b_1a_1....b_ka_k$ Aug 15 '14 at 20:35
• @JamesYang Let $a = 123$ and $b = xyz$, with $a \in A$ and $b \in B$. Is your language such that $1x2y3z = c \in C = shuffle(A, B)$? If so, that's what the automaton described here should accept. In your example, after reading $f_2$, it should go to $(0, q_1, q_1')$. This assumes when you write $a_1 = f_1f_2$ you mean $a_1b_1 = f_1f_2$. The machine that expects $B$-type input "crashes" (in the nondeterministic sense) if it gets something it can't handle. Otherwise, I'm not sure I understand what you're really asking. Aug 15 '14 at 21:02
• I'm saying is, suppose $a_1=f_1f_2\in A,b_1=g_1g_2\in B$ where $f_1,f_2,g_1,g_2$ are symbols, $a_1,b_1$ are strings So, $\widehat{\delta_{1}(a_1,q_0)}\in F_1,\widehat{\delta_{2}(b_1,q'_0)}\in F_2$. Now after reading $a_1b_1$ we go to $(0,\widehat{\delta_1(f_1g_1,q_0)},\widehat{\delta_2(f_2g_2,q'0)})$. So to fall in accept state we must have $\widehat{\delta_1(f_1g_1,q_0)}\in F_1$ ? Aug 16 '14 at 3:02