0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – ZeroUltimax Aug 15 '14 at 16:58
  • 1
    $\begingroup$ 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 $\endgroup$ – James Yang Aug 15 '14 at 17:05
  • $\begingroup$ Hmm, this k > 0 condition is quite crucial here. $\endgroup$ – Abdussami Tayyab Aug 15 '14 at 18:45
  • $\begingroup$ @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. $\endgroup$ – Patrick87 Aug 15 '14 at 18:56
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Aug 15 '14 at 21:56
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – James Yang Aug 15 '14 at 20:08
  • $\begingroup$ 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'$ $\endgroup$ – James Yang Aug 15 '14 at 20:16
  • $\begingroup$ 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$ $\endgroup$ – James Yang Aug 15 '14 at 20:35
  • $\begingroup$ @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. $\endgroup$ – Patrick87 Aug 15 '14 at 21:02
  • $\begingroup$ 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$ ? $\endgroup$ – James Yang Aug 16 '14 at 3:02

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.