patternMinor
What is the maximum number of classes resulting from partitioning by DFA as function of number of states?
Viewed 0 times
dfanumberthemaximumwhatstatesfunctionresultingclassesfrom
Problem
I was wondering whether it is possible (and if so, then how) to tell what is the maximum number of equivalence classes generated by a DFA as per Myhill-Nerode theorem (assuming it has no redundant transitions) as a function of number of accepting and rejecting states and cardinality of its alphabet.
My guess is that it should be something like $\log(n) \cdot |{\Sigma}|$, where $n$ is the number of states, since one could see this as tree of derivations created by something like left-regular grammar equivalent to the same automata, and classes would be the leafs of this tree. But this is just a guess.
My guess is that it should be something like $\log(n) \cdot |{\Sigma}|$, where $n$ is the number of states, since one could see this as tree of derivations created by something like left-regular grammar equivalent to the same automata, and classes would be the leafs of this tree. But this is just a guess.
Solution
I'm not sure what you mean by classes, but if you mean Myhill–Nerode equivalence classes, then the classical construction shows that the (unique) minimal DFA has as many states as equivalence classes.
Context
StackExchange Computer Science Q#47777, answer score: 4
Revisions (0)
No revisions yet.