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 .
Attempted by 91 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.