Question

For languages $\mathbf{A}\mathbf{and}\mathbf{B}$, let the shuffle of $\mathbf{A}\mathbf{and}\mathbf{B}$be the language

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

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

Short answer

The class of regular languages is closed under shuffle.

Step-by-step solution

Introduction 

The given two languages $\mathrm{A}\mathrm{and}\mathrm{B}$ is shuffle on the$\mathrm{A}\mathrm{and}\mathrm{B}$ is as follows:

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

Assume, ${\text{DFA}}_{\text{A}}\text{=}({\text{Q}}_{\text{A}}\text{,}\sum \text{,}{\mathrm{\delta }}_{\text{A}}{\text{,S}}_{\text{A}}{\text{,F}}_{\text{A}})$ and ${\text{DFA}}_{\text{B}}\text{=}({\text{Q}}_{\text{B}}\text{,}\sum \text{,}{\mathrm{\delta }}_{\text{B}}{\text{,S}}_{\mathrm{B}}{\text{,F}}_{\text{B}})$be the two$\text{DFA}$ s that recognizethe, $\mathrm{A}$and $\mathrm{B}$respectively. ${\text{DFA}}_{\text{Perfect-shuffle}}\text{=}(\text{Q,}\sum \text{,}\mathrm{\delta }\text{,S,F})$, and also recognizes the language is perfect shuffle on,$\mathrm{A}$ and $\mathrm{B}$.

Explanation

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

Each character should belong to ${\text{DFA}}_{\text{A}}$or ${\text{DFA}}_{\text{B}}$i.e., ${\text{a}}_{\text{i}}{\text{,b}}_{\text{i}}\in \sum$. For each character read, ${\text{DFA}}_{\text{Perfect-shuffle}}$makes moves in the corresponding$\text{DFA}$ (either ${\text{DFA}}_{\text{A}}$or ${\text{DFA}}_{\text{B}}$).

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

$\mathrm{q}={\mathrm{q}}_0$

Simplification

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

${\text{Q=Q}}_{\text{A}}\times {\text{Q}}_{\text{B}}\times \text{{A,B}}$: set of all possible states of ${\text{DFA}}_{\text{A}}$and ${\text{DFA}}_{\text{B}}$which should match with ${\text{DFA}}_{\text{Perfect-shuffle}}$.

The input alphabet for ${\text{DFA}}_{\text{Perfect-shuffle}}$is $\sum _{}^{}$.

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

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

Transition function

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

1. $\mathrm{\delta }\left(\right(\mathrm{m},\mathrm{n},\mathrm{A}),\mathrm{a})=\left({\mathrm{\delta }}_{\mathrm{A}}\right(\mathrm{m},\mathrm{a}),\mathrm{n},\mathrm{B})$
2. $\mathrm{\delta }\left(\right(\mathrm{m},\mathrm{n},\mathrm{B}),\mathrm{b})=(\mathrm{m},{\mathrm{\delta }}_{\mathrm{B}}(\mathrm{n},\mathrm{b}),\mathrm{n},\mathrm{A})$

Consider, the current state of ${\text{DFA}}_{\text{A}}$is$\mathrm{m}$ and the current state of${\text{DFA}}_{\text{B}}$ is $\mathrm{n}$. Change the current state of $\mathrm{A}$to${\mathrm{\delta }}_{\mathrm{A}}(\mathrm{m},\mathrm{a})$if the next character is to be read from${\text{DFA}}_{\text{A}}$ whenais the next character. After the character is read, read the next character from ${\text{DFA}}_{\text{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${\text{DFA}}_{\text{B}}$ when $\mathrm{b}$is the next character.

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

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