Question

For languages A and B let the perfect shuffle of A and B be the language

$\mathbf{\left\{}\mathit{\omega }\mathbf{\right|}\mathit{\omega }\mathbf{=}{\mathit{a}}_{\mathbf{1}}{\mathit{b}}_{\mathbf{1}}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{a}}_{\mathbf{k}\mathbf{ }}{\mathit{b}}_{\mathbf{k}}\mathbf{,}\mathit{w}\mathit{h}\mathit{e}\mathit{r}\mathit{e}\mathbf{ }\mathbf{ }{\mathit{a}}_{\mathbf{1}}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{a}}_{\mathbf{k}\mathbf{ }}\mathbf{\in }\mathbf{ }\mathit{A}\mathbf{ }\mathbf{ }\mathit{a}\mathit{n}\mathit{d}\mathbf{ }\mathbf{ }{\mathit{b}}_{\mathbf{1}}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{b}}_{\mathbf{k}}\mathbf{\in }\mathbf{ }\mathit{B}\mathbf{,}\mathit{e}\mathit{a}\mathit{c}\mathit{h}\mathbf{ }\mathbf{ }{\mathit{a}}_{\mathbf{i}}\mathbf{,}{\mathit{b}}_{\mathbf{i}}\mathbf{\in }\mathbf{\sum }\mathbf{\}}\mathbf{.}$

Show that the class of regular languages is closed under perfect shuffle.

Short answer

The class of regular languages is closed under perfect shuffle.

Step-by-step solution

The given two languages. The language is perfect shuffle on A and B is as follows

$\left\{\mathrm{\omega }\right|\mathrm{\omega }={\mathrm{a}}_1{\mathrm{b}}_1...{\mathrm{a}}_{\mathrm{k} }{\mathrm{b}}_{\mathrm{k}},\mathrm{where} {\mathrm{a}}_1...{\mathrm{a}}_{\mathrm{k} }\in \mathrm{A} \mathrm{and} {\mathrm{b}}_1...{\mathrm{b}}_{\mathrm{k}}\in \mathrm{B},\mathrm{each} {\mathrm{a}}_{\mathrm{i}}{\mathrm{b}}_{\mathrm{i}}\in \sum .$

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

DFA for perfect shuffle switches

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\in \sum$. 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}}$.

DFA

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

$\mathrm{Q}={\mathrm{Q}}_{\mathrm{A}}\times {\mathrm{Q}}_{\mathrm{B}}\times \{\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}}\times {\mathrm{F}}_{\mathrm{B}}\times \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}}$

.

Transition function

The transition function $\delta$is,

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

2. $\delta \left(\right(m,n,B),b)=(m,{\delta }_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${\delta }_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{\delta }}_{\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.