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 ______.

Question

Question

This question was previously asked in

GATE CS 2019 Official Paper

Answer 1

Total number of bijective from A → A where A = {1,2 3, 4, 5} is 5! = 120.

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