輸入符號{0,1,2}，最後一個符號是1的最小DFA中的狀態數是多少？

Question

四個選項： -

A. 8

B. 9

C. 6

D.無

可以請人解釋圖解答案。 。

Answer 1

B.9

每當問題說右邊的第n個符號是固定的，輸入語言有m個符號時，最小dfa的答案是m^n。所以3^2 = 9

Answer 2

接受的答案是錯誤的。請看下面的最小DFA的語言：

q e q' 
q0 0 q0 
q0 1 q1 
q0 2 q0 
q1 0 q2 
q1 1 q3 
q1 2 q2 
q2 0 q0 
q2 1 q1 
q2 2 q0 
q3 0 q2 
q3 1 q3 
q3 2 q2 

對方的回答得到它錯誤的原因是因爲在這種語言符號0和2之間沒有真正的區別。符號可能是「1」和「不是1」。當你正確地認識到這一點時，最小數量的狀態確實是另一個答案指出的：2^2 = 4個狀態。如果這更容易消化，這是一個粗略的圖。

/------0,2--------\ 
|   /---1--\ | 
v  v  \| 
q0 --1-> q1 -0,2-> q2 
     |  ^
     1   | 
     v   | 
     q3---0,2--/ 
     /^ 
     \1/