Question 58

Let $S = \{1, 2, 3, 4, 5\}$. The alphabet $\Sigma$ is the set of all bijections (permutations) from $S$ to $S$. Under function composition $\circ$, this set forms the symmetric group $S_5$, which contains $|S_5| = 5! = 120$ elements.

For any string $x = x_1 x_2 \dots x_n \in \Sigma^*$, the accumulated composition $\pi(x) = x_1 \circ x_2 \circ \dots \circ x_n$ is a specific permutation in $S_5$. The empty string $\epsilon$ evaluates to the identity permutation $\pi(\epsilon) = id$.

The language is defined as $L = \{x \in \Sigma^* \mid \pi(x) = id\}$.

According to the Myhill-Nerode theorem, the minimum number of states in any deterministic finite automaton (DFA) accepting $L$ equals the number of equivalence classes of the right congruence relation $\sim_L$, where:

Notice that $uw \in L$ means $\pi(u) \circ \pi(w) = id$, which is equivalent to $\pi(w) = (\pi(u))^{-1}$.
Similarly, $vw \in L$ means $\pi(w) = (\pi(v))^{-1}$.
Therefore:

• If $\pi(u) = \pi(v)$, then $(\pi(u))^{-1} = (\pi(v))^{-1}$, so for any $w$, $uw \in L \iff vw \in L$. Thus $u \sim_L v$.
• If $\pi(u) \ne \pi(v)$, their inverses are distinct. Choosing $w$ as the single symbol representing the bijection $(\pi(u))^{-1} \in \Sigma$, we have $\pi(uw) = id$ (so $uw \in L$), but $\pi(vw) = \pi(v) \circ (\pi(u))^{-1} \ne id$ (so $vw \notin L$). Thus $u \not\sim_L v$.

Consequently, two strings are equivalent under $\sim_L$ if and only if their compositions yield the exact same permutation in $S_5$.

Since all 120 permutations in $S_5$ are reachable (each permutation is a single symbol in $\Sigma$), there are exactly 120 distinct equivalence classes. Hence, the minimum number of states in any DFA accepting $L$ is 120.