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.

  • $\begingroup$ seems maybe you are interested in the relationship between nonminimized and minimized DFAs where every state in the minimized DFA is a "class"...? $\endgroup$ – vzn Oct 1 '15 at 18:30
  • $\begingroup$ @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. $\endgroup$ – wvxvw Oct 1 '15 at 18:33
  • $\begingroup$ 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. $\endgroup$ – vzn Oct 1 '15 at 18:39
  • $\begingroup$ @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. $\endgroup$ – wvxvw Oct 1 '15 at 18:49
  • $\begingroup$ possibly look into hidden markoff models, PAC learning both of which have connections to DFAs or try dropping by Computer Science Chat $\endgroup$ – vzn Oct 1 '15 at 20:00

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.

  • $\begingroup$ Yes, I do mean Myhill-Nerode equivalence classes. And I somehow missed this point in the theorem... My motivation for asking this question was me thinking of a possibility of using statistical methods for partitioning some data (eg. DNA strings) into classes and then try to guess a DFA for the language, instead of creating a DFA for each specimen and taking a union of all of them. Would you have any idea of whether this is plausible, or not? $\endgroup$ – wvxvw Oct 1 '15 at 17:19
  • 1
    $\begingroup$ I believe this is called "learning DFAs", and there is some relevant literature. $\endgroup$ – Yuval Filmus Oct 1 '15 at 17:21

You mention motivations in comments, but in this question you seem to be asking about how to determine worst case bounds on a/the "compression ratio" of an unminimized DFA versus a minimized one. This is indeed studied systematically/scientifically but note that an unminimized DFA can have unbounded redundant states so this question must be formalized more carefully/cleverly to come up with some kind of metric.

Here are two example papers in the area that study it empirically. The first is in the context of router systems that use DFA rules for examining packets. The 2nd uses randomly generated DFAs somewhat analogous to Erdos-Renyi graphs and examines efficiency of different algorithms.


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.