91Ó°ÊÓ

$\left\{\mathrm{Ó\neg }\right|\mathrm{Ó\neg }={\mathrm{a}}_1{\mathrm{b}}_1...{\mathrm{a}}_{\mathrm{k} }{\mathrm{b}}_{\mathrm{k}},\mathrm{where} {\mathrm{a}}_1...{\mathrm{a}}_{\mathrm{k} }∈ \mathrm{A} \mathrm{and} {\mathrm{b}}_1...{\mathrm{b}}_{\mathrm{k}}∈ \mathrm{B},\mathrm{each} {\mathrm{a}}_{\mathrm{i}}{\mathrm{b}}_{\mathrm{i}}∈∑.$

Assume, $DF{A}_A=(Q_A,∑,{\mathrm{δ}}_A,S_A,F_A)$and $DF{A}_B=(Q_B,∑,{\mathrm{δ}}_B,S_B,F_B)$be the two DFAs that recognize the A and B respectively. ${\mathrm{DFA}}_{\mathrm{Perfect}-\mathrm{shuffle}}=(\mathrm{Q},∑,\mathrm{δ},\mathrm{S},\mathrm{F})$, and also recognizes the language is perfect shuffle on A, and B

The DFA for perfect shuffle switches from ${\mathrm{DFA}}_{\mathrm{A}}$to ${\mathrm{DFA}}_{\mathrm{B}}$after each character is read and it tracks the current states of ${\mathrm{DFA}}_{\mathrm{A}}$, and ${\mathrm{DFA}}_{\mathrm{B}}$.

Each character should belong to ${\mathrm{DFA}}_{\mathrm{A}}$or ${\mathrm{DFA}}_{\mathrm{B}}$i.e., $a_i,b_i∈∑$. For each character read,${\mathrm{DFA}}_{\mathrm{Perfect}-\mathrm{shuffle}}$ makes moves in the corresponding DFA(either$\mathrm{DF}{A}_{\mathrm{A}}$ or ${\mathrm{DFA}}_{\mathrm{B}}$).

After the whole string is read, if both${\mathrm{DFA}}_{\mathrm{A}}$ and ${\mathrm{DFA}}_{\mathrm{B}}$reaches to the final state, then the input string is accepted by ${\mathrm{DFA}}_{\mathrm{Perfect}-\mathrm{shuffle}}$.

The ${\mathrm{DFA}}_{\mathrm{Perfect}-\mathrm{shuffle}}$is defined as follows:

$\mathrm{Q}={\mathrm{Q}}_{\mathrm{A}}×{\mathrm{Q}}_{\mathrm{B}}×\{\mathrm{A},\mathrm{B}\}$: set of all possible states of ${\mathrm{DFA}}_{\mathrm{A}}$and localid="1663235489142" ${\mathrm{DFA}}_{\mathrm{B}}$which should match with localid="1663235493556" ${\mathrm{DFA}}_{\mathrm{Perfect}-\mathrm{shuffle}}$.

The input alphabet for $DF{A}_{\mathrm{Perfect}-\mathrm{shuffle}}$is.

$\mathrm{q}=\left({\mathrm{q}}_{\mathrm{A}},{\mathrm{q}}_{\mathrm{B}},\mathrm{A}\right)$:${\mathrm{q}}_{\mathrm{A}}$and ${\mathrm{q}}_{\mathrm{B}}$are the initial states for ${\mathrm{DFA}}_{\mathrm{A}}$and ${\mathrm{DFA}}_{\mathrm{B}}$respectively. ${\mathrm{DFA}}_{\mathrm{Perfect}-\mathrm{shuffle}}$starts with ${\mathrm{q}}_{\mathrm{A}}$in ${\mathrm{DFA}}_{\mathrm{A}}$, ${\mathrm{q}}_{\mathrm{B}}$in${\mathrm{DFA}}_{\mathrm{B}}$and the next character should be read from ${\mathrm{DFA}}_{\mathrm{A}}$

$\mathrm{F}={\mathrm{F}}_{\mathrm{A}}×{\mathrm{F}}_{\mathrm{B}}×\left\{\mathrm{A}\right\}$: ${\mathrm{F}}_{\mathrm{A}}$ and${\mathrm{F}}_{\mathrm{B}}$ are the final states for${\mathrm{DFA}}_{\mathrm{A}}$ and${\mathrm{DFA}}_{\mathrm{B}}$ respectively. ${\mathrm{DFA}}_{\mathrm{Perfect}-\mathrm{shuffle}}$ Accepts if both${\mathrm{DFA}}_{\mathrm{A}}$ and${\mathrm{DFA}}_{\mathrm{B}}$ reaches to the final states and the next character should be read from${\mathrm{DFA}}_{\mathrm{A}}$

The transition function $\mathrm{δ}$is,

1. $  \mathrm{δ}\left(\right(m,n,A),a)=\left({\mathrm{δ}}_A\right(m,a),n,B)$

2. $ \mathrm{δ}\left(\right(m,n,B),b)=(m,{\mathrm{δ}}_B(n,b),n,A)$

Consider, the current state of ${\mathrm{DFA}}_{\mathrm{A}}$is m and the current state ${\mathrm{DFA}}_{\mathrm{B}}$of is n. Change the current state of A to${\mathrm{δ}}_A(m,a)$ if the next character is to be read${\text{DFA}}_A$ from when a is the next character. After the character is read, read the next character from ${\mathrm{DFA}}_{\mathrm{B}}$.

Change the current state of B to${\mathrm{δ}}_{\mathrm{B}}(\mathrm{n},\mathrm{b})$ if the next character is to be read from${\mathrm{DFA}}_{\mathrm{B}}$ when b is the next character.

The language L is said to be regular if there exist an FA that recognizes the language L. Here, the${\mathrm{DFA}}_{\mathrm{Perfect}-\mathrm{shuffle}}$ is defined for the languageperfect shuffle.

Therefore, the class of regular languages is closed under perfect shuffle.