# Language of all sequences of permutations whose product is the identity

Let $$\Sigma$$ be the set of all permutations in $$S_n$$. What is the minimum number of states in a DFA accepting the language of all words over $$\Sigma$$ which multiply to the identity permutation?

For example, if $$n=2$$, then $$\Sigma$$ consists of two mappings, the identity mapping $$\iota$$ and the transposition $$\tau$$. The language in this case consists of all words containing an even number of $$\tau$$'s.

• I explained more. Now is it clear? – Srestha Feb 14 '19 at 9:11
• This function contains only n! bijective function. right? Now if we need to put it in a DFA, then is minimised DFA also contain n! states?? – Srestha Feb 14 '19 at 10:20

It is easy to check that the equivalence classes of the Myhill–Nerode relation correspond to all words multiplying to a certain permutation. Therefore the minimal DFA contains $$n!$$ states.
If the empty word is not allowed, there are $$n!+1$$ equivalence classes, one of them consisting only of $$\epsilon$$.
• The answer might depend on which direction we're composing the functions. I'm sure you can work it out on your own. Try the case $n=2$ first. – Yuval Filmus Feb 14 '19 at 13:34