# Show that the class of regular languages is closed under shuffle

For languages A and B, let the shufﬂe of A and B be the language
$\{w| w = a_1b_1···a_kb_k,$ where $a_1···a_k ∈ A$ and $b_1···b_k ∈ B,$ each$a_i,b_i ∈ Σ^∗\}$.
Show that the class of regular languages is closed under shufﬂe.

Approach: If A and B are regular, then there exists an NFA R and T that recognizes them. I was thinking I could run R and T in parallel, so I would start running R by processing $a_1$ and then by using non-determinism, I would jump to the NFA T to process $b_1$. In this process I make sure that both NFAs aren't executed the original way because that would result in accepted strings that are not in the language, so I try to disconnect the edges in each NFA to jump to the other NFA and then disconnect again the edges of this NFA to come back to the previos NFA.. Is this process clear?

Here is the proof, but some lines are a bit unclear to me.

I can't understand d)i. I don't understand how the transition function works. How does it detect whether we are at DFA A OR B?

There is a problem in that solution because it says that $N$ should accept the empty string. However, the shuffle of two languages $A$ and $B$ contains the empty word if and only if both $A$ and $B$ contain it.

Aside from that, the solution is OK. The constructed automaton uses nondeterminism to guess how the input string $w$ is to be divided into substrings $a_1, a_2, \ldots, a_k$ and $b_1,b_2, \ldots, b_k$ such that $A$ contains $a_1 \cdots a_k$ and $B$ contains $b_1 \cdots b_k$.

Input letters are consumed by either the acceptor of $A$ or the acceptor of $B$. In its infinite wisdom, the nondeterministic automaton doles out individual letters to the right acceptor, if there is indeed a way to split the input word into two words, one in $A$ and the other in $B$.

The new initial state $q_0$ is added because they want to accept the empty string regardless. Otherwise, taking $(q_A,q_B)$ as initial state would work just fine.

Let's prove that the construction is correct. Suppose $w = a_1b_1 \cdots a_kb_k$, with $a_1 \cdots a_k \in A$ and $b_1 \cdots b_k \in B$. When reading a letter from $a_i$, $N$ makes a transition that changes the first component of the state, and leaves the second component unchanged. Likewise, when it reads a letter from $b_i$. Nondeterminism allows $N$ to correctly break up $w$ before seeing it all. When the whole string has been read, the state is accepting for both $A$ and $B$. Hence $N$ accepts.

Suppose $w$ is accepted by $N$. Then there is an accepting run of $N$ on $w$. This run can be divided into maximal segments that are uniform with respect to the type of transitions. That is, in each segment one component of the state does not change. A segment is an $a_i$ if the second component of the state is unchanged, and a $b_i$ otherwise.

Since $a$-segments and $b$-segments alternate, the imbalance between the number of $a$-segments and $b$-segments is at most one. We need to consider four cases.

1. Even number of segments with an $a$-segment first. This is the easiest case: nothing needs to be done, besides separating the $a$'s from the $b$'s, to find the two words $a_1 \cdots a_k \in A$ and $b_1 \cdots b_k \in B$.

2. Even number of segments with a $b$-segment first. In this case we sandwich the segments between two empty segments. The one at the beginning becomes $a_0$, and the one at the end becomes $b_k$. We then proceed as in Case 1.

3. Odd number of segments with an $a$-segment first. We add an empty segment at the end to act as $b_k$.

4. Odd number of segments with a $b$-segment first. We add an empty segment at the beginning to act as $a_1$.

In conclusion, if $w$ is accepted by $N$, it is in the shuffle of $A$ and $B$.

Another, perhaps more intuitive way to see why the constructed $N$ works is this: Suppose $w = a_1b_1 \cdots a_kb_k$, with $a_1\cdots a_k \in A$ and $b_1\cdots b_k \in B$. Let

$$a_ib_i = a_{i1}a_{i2} \cdots a_{in_i} b_{i1} b_{i2} \cdots b_{im_i} \enspace,$$

where the $a_{ij}$ and $b_{ik}$ are strings of length 1; that is, they are letters in $\Sigma$. Then we can also write

$$a_ib_i = a_{i1} \,\epsilon\, a_{i2} \,\epsilon\, \cdots \,\epsilon\, a_{in_i} b_{i1} \,\epsilon\, b_{i2} \,\epsilon\, \cdots \,\epsilon\, b_{im_i} \enspace.$$

That is, we can interleave empty strings and enforce the constraint that each $a_i$ and $b_i$ is of length less than or equal to 1. This interpretation allows us to see why the automaton effectively decides for each letter which of the two acceptors is going to consume it.

• How could you prove this? – daniel Feb 17 '17 at 6:20
• The other thing that really confuses me is that they are referring to input as characters rather than strings. I know that strings are processed character by character, but they don't make any point on it. – daniel Feb 17 '17 at 6:23
• It's a shuffle not a perfect shuffle. Are u considering the fact that $a_i$ are strings and not characters? – daniel Feb 17 '17 at 6:29
• Ooops! It's not a perfect shuffle. OK. Never mind. I got carried away. – Fabio Somenzi Feb 17 '17 at 6:31
• I am afraid that the machine would accept strings that are not in the language . Ex $a_1a_2b_1b_2$ – daniel Feb 24 '17 at 10:01

I do not think the solution works.

Given:

$A = \{ a_1a_2, a_1a_2a_3a_4 \}$
$B = \{ b_1b_2\}$

And this definition of shuffle:

For languages A and B, let the shufﬂe of A and B be the language
$\{w| w = a_1b_1···a_kb_k,$ where $a_1···a_k ∈ A$ and $b_1···b_k ∈ B,$ each$a_i,b_i ∈ Σ^∗\}$.

$Shuffle(A,B) = \{\epsilon, a_1b_1a_2b_2\}$

But the constructed NFA would accept $\{\epsilon, a_1b_1a_2b_2, a_1b_1a_2b_2a_3a_4\}$

Arguably, the $\epsilon$ also shouldn't be there.

This homework from Roger Jestes does what I was thinking about. Add another item to the state that indicates which machine the last symbol was sent to. That determines which machine the next symbol will be sent to.

$Q = (Q_A x Q_B x {1, 2})$ Where 1 means B consumed the last symbol and 2 means a consumed the last symbol.