是否可以確定最小DFA中的狀態數量而不顯式構造它？

Question

根據任何語言，是否有任何簡短答案或公式來確定DFA中的州數量？更確切地說，是否可以確定最小DFA中的狀態數量，而無需明確構造它？

Answer 1

那麼我不知道「短」，但有一個啓發式，可以使用。這基本上是對Myhill-Nerode Theorem的結果的重述。

給定一個字母，這是在該字母的所有字符串的一個子集語言，說兩個字符串X和ÿ是等價的，如果其他任何字符串ž的串連XZ和YZ既可以使用該語言，也可以不使用該語言。 （注意：ž可以是空字符串）

例如，如果字母表只是0和1，語言是「在11結束所有字符串」，然後字符串「0010」和「1110」是等效的，因爲如果z以11結尾，則兩個級聯都是使用該語言，並且如果z沒有以11結尾，則兩個級聯都不在該語言中。請注意，字符串「0001」並不等同於另外兩個，因爲如果ž是「1」，然後串聯「0001」 +「1」是語言，但串聯「0010」 +「1」不在語言中。

然後，該語言的最小DFA中的狀態數是根據該「等價」定義下的等價類的數量。

在從之前的例子中，等價類是結束一個1但不要「不以1結尾的字符串」（所以，在0或空字符串結尾的字符串），「串以11結尾「和」以11結尾的字符串「。因此，此語言的最小DFA包含三種狀態。

我所知道的唯一的應用是證明了「在一些固定的基地b是由ň整除號」常規語言至少ň狀態需要。