Let A and B be regular languages. We define the following operation

PSHUFFLE.

PSHUFFLE$($A$,$B$)=\{$w $|$ w $=$ a$1$b$1...$akbk, where a$1...$ak in A and b$1...$bk in B$,$

each ai$,$ bi in $\backslash$Sigma $\}.$

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