$(15$ points$)$ Let A and $B$ be regular languages. We define the following operation

PSHUFFLE.

PSHUFFLE$($A$,$B$)=\{\begin{array}{c}w|w=a_1{b}_{1}dots{a}_k{b}_k\end{array},$ where $a_{1}dots{a}_k$inA and $b_{1}dots{b}_k$inB,

each $\{$:$a_i,b_{i}in\}.$

Show that the class of regular languages is closed under PSHUFFLE. You will need

to write out a proof. Hint, use a proof by construction technique.