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

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.

• seems maybe you are interested in the relationship between nonminimized and minimized DFAs where every state in the minimized DFA is a "class"...? – vzn Oct 1 '15 at 18:30
• @vzn my motivation is rather to use some heuristics / statistical methods to try to guess the DFA for a given language (assuming I don't have a perfect knowledge of the language / the data may contain errors), and such that DFA may not generate all observed data, but covers a large fraction of it. – wvxvw Oct 1 '15 at 18:33
• there is maybe some question trying to break free here but it doesnt seem to make much sense right now. DFAs of arbitrary size can represent any finite data. so there has to be some other constraint. how well a DFA approximates noisy data would be data & algorithm dependent. – vzn Oct 1 '15 at 18:39
• @vzn well, obviously I'd be looking for a small DFA. To better illustrate the idea, think of a program which tries to guess the programming language of the example code. A human would perform a number of actions in order to figure out, and these actions can be described as automata. Statistical methods on the other hand may offer clustering as a basis for recognizing which actions will set one language apart from the rest. My idea is in that rather than learning a vector of features, one could try to learn a DFA of features. – wvxvw Oct 1 '15 at 18:49
• possibly look into hidden markoff models, PAC learning both of which have connections to DFAs or try dropping by Computer Science Chat – vzn Oct 1 '15 at 20:00