GATE CS 2019 Q48 — Regular Expressions and Finite Automata

The set of all bijections from $\{1, \dots, 5\}$ to $\{1, \dots, 5\}$ under the composition operation $\circ$ forms the symmetric group $S_5$.

Let $G = S_5$ be this group. The identity element of $G$ is $id$, and the size of the group is $|G| = 5! = 120$.

DFA Construction

We can construct a DFA $M = (Q, \Sigma, \delta, q_0, F)$ to accept $L$ as follows:

• States ($Q$): The states correspond to the elements of the group $G$. Thus, $Q = S_5$.
• Start State ($q_0$): The identity element $id$.
• Accepting States ($F$): The singleton set $\{id\}$.
• Transition Function ($\delta$): For any state $g \in G$ and input symbol $x \in \Sigma$, the transition is defined by group multiplication: $$\delta(g, x) = g \circ x$$

Proof of Minimality

To show that this DFA is minimal, we must prove that all states in $Q$ are pairwise distinguishable:

Let $g_1, g_2 \in G$ be two distinct states ($g_1 \neq g_2$). Consider the string $w = g_1^{-1} \in \Sigma^*$ (since every bijection has a unique inverse in $S_5$):

• Processing $w$ from state $g_1$ leads to: $$\delta(g_1, g_1^{-1}) = g_1 \circ g_1^{-1} = id \in F$$
• Processing $w$ from state $g_2$ leads to: $$\delta(g_2, g_1^{-1}) = g_2 \circ g_1^{-1} \neq id \notin F \quad (\text{since } g_1 \neq g_2)$$

Since $w$ distinguishes $g_1$ and $g_2$, no two states in the DFA can be merged. Thus, the DFA is minimal.

The minimum number of states is equal to the number of elements in $S_5$: