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

Q. 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 𝑥 =𝑥₁ 𝑥₂ ⋯ 𝑥_𝑛 ∈ Σ^𝑛, 𝑛 ≥ 0 , let 𝜋(𝑥) = 𝑥₁ ∘ 𝑥₂ ∘ ⋯ ∘ 𝑥_𝑛. Consider the language 𝐿 = {𝑥 ∈ Σ^∗| 𝜋(𝑥) = 𝑖𝑑 }. The minimum number of states in any DFA accepting 𝐿 is

Ans:

The DFA for accepting L will have 5! = 120 states, since we need one state for every possible permutation function on 5 elements. So, answer is 120.