5
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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
    Commented Oct 1, 2015 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
    Commented Oct 1, 2015 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
    Commented Oct 1, 2015 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
    Commented Oct 1, 2015 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
    Commented Oct 1, 2015 at 20:00

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Oct 1, 2015 at 17:19
  • 1
    $\begingroup$ I believe this is called "learning DFAs", and there is some relevant literature. $\endgroup$
    – Yuval Filmus
    Commented Oct 1, 2015 at 17:21
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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