The operation of shuffle is important in the theory of concurrent sys$-$

tems. If $x,$yin${}^{**},$ we write $x||y$ for the set of all strings that can be

obtained by shuffling strings $x$ and $y$ together like a deck of cards; for

example,

$ab||cd=\{abcd,$acbd,acdb,cabd,cadb,cdab$\}.$

The set $x||y$ can be defined formally by induction:

$lon||y={?}^{\text{d}\text{e}\text{f}}\{y\},$

$x||lon={?}^{\text{d}\text{e}\text{f}}\{x\},$

$xa||yb={?}^{\text{d}\text{e}\text{f}}(x||yb)*\{a\}(xa||y)*\{b\}.$

The shuffle of two languages A and $B,$ denoted $A||B,$ is the set all

strings obtained by shuffling a string from A with a string from $B$ :

$A||B(={?}^{\text{d}\text{e}\text{f}})u_{\{\begin{array}{c}\text{:}[xinA]\\ \text{y}\text{i}\text{n}\text{B}\end{array}}x||y.$

For example,

$\{ab\}||\{cd,e\}=\{abe,$aeb,eab,abcd,acbd,acdb,cabd,cadb,cdab$\}.$

$($a$)$ What is $(01{)}^{**}||(10{)}^{**}?$

$($b$)$ Show that if A and $B$ are regular sets, then so is $A||B.($Hint:

Put a pebble on a machine for A and one on a machine for $B.$

Guess nondeterministically which pebble to move. Accept if both

pebbles occupy accept states.$)$