Is it possible to determine the number of states in a minimal DFA without explicitly constructing it?

Question

Is there any short answer or formula for determining the number of states in a DFA according to any language? more precisely is it possible to determine the number of states in a minimal DFA without explicitly constructing it?

Answer 1

Well I don't know about "short", but there is a heuristic that can be used. This is basically a restatement of the result of the Myhill-Nerode Theorem.

Given an alphabet and a language that is a subset of all strings over that alphabet, say that two strings x and y are equivalent if for any other string z the concatenations xz and yz are either both in the language or both not in the language. (note that z can be the empty string)

For example, if the alphabet is just 0 and 1, and the language is "all strings that end in 11", then the strings "0010" and "1110" are equivalent, because if z ends in 11 then both concatenations are in the language and if z does not end in 11, neither concatenation is in the language. Note that the string "0001" is not equivalent to those other two, because if z is "1", then the concatenation "0001" + "1" is in the language, but the concatenation "0010" + "1" is not in the language.

Then, the number of states in a minimal DFA for the language is the number of equivalence classes under this definition of "equivalent".

Following the example from before, the equivalence classes are "strings that do not end in a 1" (so, strings that end in 0 or the empty string), "strings that end in a 1 but do not end in 11", and "strings that end in 11". Therefore, the minimal DFA for this language consists of three states.

The only application I know of is the proof that the regular language for "numbers in some fixed base b that are divisible by n" requires at a minimum n states.