World's most popular travel blog for travel bloggers.

[Answers] What is the maximum number of classes resulting from partitioning by DFA as function of number of states?

, , No Comments
Problem Detail: 

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.

Asked By : wvxvw

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback