非決定論的有限オートマトンを描こうとすると

Question

私は有限オートマトンの話題を理解するのに苦労しています。

私はシンプルなものを描くことができるが、私はに尋ねる練習問題があります。

デザイン非決定性有限オートマトンΣ= {0,1}を受け入れます。非決定性有限オートマトンは、最大で2つのゼロと少なくとも2つのものを持つすべての文字列を決定できるはずです。

どうすればよいですか？ここで

Answer 1

は、言語の最小DFAです（最小限のDFAのNFAのDFAされている）：

   0   0   0 
----->(0,0)----->(1,0)----->(2,0)-------+ 
     |   |   |   | 
     | 1  | 1  | 1  | __ 
     |   |   |   |/\ 
     V 0  V 0  V 0 V V | 0, 1 
     (0,1)----->(1,1)----->(2,1)----->dead--/ 
     |   |   |  ^
     | 1  | 1  | 1  | 
     |   |   |   | 
     V 0  V 0  V 0 | 
     (0,2)----->(1,2)----->(2,2)-------+ 
    /^  /^  /^ 
    1 | | 1 | | 1 | | 
    \_/  \_/  \_/ 

アイデアは状態(x,y)がxゼロとyなものを見た後訪問されていることです。 2つのゼロを見て、別のゼロを参照すると、ストリングはデッド状態に遷移することによって拒否されます。あなたが2つを見たなら、あなたが好きなだけ多く見ることができます。形式(x,2)の州は受理しています。