Let Σ be the set of all bijections from {1, … , 5} to {1, … , 5}, where 𝑖𝑑…
2019
Let Σ be the set of all bijections from {1, … , 5} to {1, … , 5}, where 𝑖𝑑 denotes the identity function, i.e. 𝑖𝑑(𝑗) = 𝑗, ∀𝑗. Let ∘ denote composition on functions. For a string 𝑥 = 𝑥1 𝑥2 ⋯ 𝑥𝑛 ∈ Σ𝑛 , 𝑛 ≥ 0 , let 𝜋(𝑥) = 𝑥1 ∘ 𝑥2 ∘ ⋯ ∘ 𝑥𝑛. Consider the language 𝐿 = {𝑥 ∈ Σ∗ | 𝜋(𝑥) = 𝑖𝑑 }. The minimum number of states in any DFA accepting 𝐿 is .
Answer: 120 — Key idea: view the alphabet as the group of permutations and use group multiplication to build the DFA. The alphabet Σ is the symmetric group S5, so |Σ| = 5!…
Attempted by 99 students.
Show answer & explanation
Correct answer: 120
Key idea: view the alphabet as the group of permutations and use group multiplication to build the DFA.
The alphabet Σ is the symmetric group S5, so |Σ| = 5! = 120.
Construct a DFA with one state for each permutation g ∈ S5. The start state is the identity id, and the only accepting state is id. On input a ∈ Σ from state p, move to p ∘ a. This DFA accepts exactly those words whose composed product equals id, so 120 states suffice.
Minimality: any two distinct permutations g ≠ h are distinguishable. Take the suffix w = g⁻¹. From state g reading w reaches id (accepting), while from state h reading w reaches h ∘ g⁻¹ ≠ id (non-accepting). Thus no two states can be merged, so any DFA needs at least 120 states.
Therefore the minimum number of states in any DFA accepting L is 120.