1,177 views
0 votes
0 votes

The shuffle of two strings w and x is the set of all strings that one can get by interleaving the positions of w and x in any way.More precisely,shuffle(w,x) is the set of strings z such that

1)Each position of z canbe assigned to w or x,but not both

2)The position of z assigned to w form w when read from left to right.

3)The position of z assigned to x from x when read from left to right.

For example,if w=01 and x=110 then shuffle(01,110) is the set of strings {01110,01101,10110,01011,11001,11010}.

Q) Show that if L1 and L2 are both regular languages,then so is shuffle(L1,L2)

1 Answer

0 votes
0 votes

For the sake of simplicity let us rename the two languages $L_1$ and $L_2$ as $A$ and $B$ respectively.

Let $M_A(Q_A,\Sigma,\delta_A,q_{0A},F_A)$ and $M_B(Q_B,\Sigma,\delta_B,q_{0B},F_B)$ be two DFA accepting the language $A$ and $B$ respectively.

To prove that the language generated by $shuffle(A,B)$ is regular, we define a NFA $M(Q,\Sigma,\delta,q_{0},F)$ which accept all strings of language $shuffle(A,B)$. 

Let, $Q = Q_A \times Q_B$, $q_0 = (q_{0A}, q_{0B})$ and $F = F_A \times F_B$. Then we define the transition function of $M$ as follows

$$\delta((q_a, q_b), s) = {(\delta_A(q_a,s),q_b)} \cup {(q_a,\delta_A(q_b,s))}$$

This machine will accept exactly those string which are in $shuffle(A,B)$ and equivalently $shuffle(L_1,L_2)$ and thus completes the proof that the language $shuffle(L_1,L_2)$ is regular.


HTH

edited by

Related questions

8 votes
8 votes
3 answers
1
2 votes
2 votes
3 answers
2
iarnav asked Sep 15, 2017
4,608 views
Can someone explain what's this prefix property, there's no proper explanation on google and may you please explain with taking some examples. Thanks.
2 votes
2 votes
0 answers
3
Shubhanshu asked Aug 28, 2017
2,553 views
Construct the DPDA with empty stack and final state method for the language L = ${ a^n b^n / n>= 0}$.