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.

  • $\begingroup$ I explained more. Now is it clear? $\endgroup$ – Srestha Feb 14 '19 at 9:11
  • $\begingroup$ 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?? $\endgroup$ – Srestha Feb 14 '19 at 10:20

You haven't stated what happens to the empty word – I'm assuming it's accepted.

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

  • $\begingroup$ what about in case of injective mapping? $\endgroup$ – Srestha Feb 14 '19 at 13:33
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 14 '19 at 13:34
  • $\begingroup$ Can u give some good link for it, I have not seen such concept before $\endgroup$ – Srestha Feb 14 '19 at 13:47
  • $\begingroup$ Neither have I. The problems which are more interesting to solve are those that we haven't seen before. $\endgroup$ – Yuval Filmus Feb 14 '19 at 13:47
  • $\begingroup$ We are concluding it with respect to equivalent class. right? and we are assuming number of states in DFA and equivalence class is same. But is there any possibility that number of states, less than number of permutation , that means that is less than n! ?? $\endgroup$ – Srestha Feb 14 '19 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.