非確定性有限自動化問題

我正在做一些研究，並且當它處理1時，我對這個小的不確定性算法有點困惑。我知道它會用q1分成一個品牌，因爲0或1會重新導向回來， q2的退出箭頭是1，但爲什麼會分成q3？我覺得我會誤解（0，空字符串），任何澄清都會很棒。非確定性有限自動化問題

enter image description here

2011-09-19 jfisk

空字符串意味着你可以把它在任何時間。在這種情況下，1將把它帶到q2，因爲q2有一個空字符串箭頭到q3。它也將立即採取，而不必獲得輸入的下一位。

2011-09-19 03:56:01 quasiverse

啊好的。如果是這樣的話，那麼爲什麼第四名的分支會在q2下降？ – jfisk

...因爲沒有箭頭從輸入'1'離開q2，因此分支死亡 – Nemo

它從q1開始，然後得到輸入1.它可以轉到q1，q2或q3，然後獲得下一個輸入。在這種情況下轉到q2，獲取下一個輸入並轉到q3與直接轉到q3並獲取後面的輸入相同。基本上，它沒有顯示它，因爲它與它旁邊的q3路徑重複。 – quasiverse

回答