Question 7829 – Theory-of-Computation

Let Σ be the set of all bijections from {1, …, 5} to {1, …, 5}, where id denotes the identity function i.e. id(j) = j,∀j. Let º denote composition on functions. For a string x = x₁ x₂ … x_n ∈ Σⁿ, n ≥ 0. Let π(x) = x₁ º x₂ º … º x_n.

Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of  states in any DFA accepting L is ______.

Correct Answer: A