7

找不到任何肯定的東西。而具有任何epsilon轉換的NFA是一個epsilon-NFA? 謝謝。DFA可以有epsilon/lambda轉換嗎?

+0

你說的拉姆達轉型意味着什麼? –

+0

有些書使用lambda而不是epsilon。這是同一件事。 – liwing

回答

9

DFA不會有小量transitions.If它有它,它可以從當前狀態到另一個狀態交通沒有任何輸入,即什麼也沒有,甚至沒有{}或披。根據定義,我們知道輸入必須來自輸入集。 希望這會清除您的疑問......

+0

如果這個過渡到最終狀態會怎麼樣?如本文件第225頁圖3.51所示http://www.univasf.edu.br/~marcus.ramos/lfa-2008-1/Secao%2003-06.pdf。 – liwing

+0

哇..圖像現在是不言自明的..你看,q0過渡到q3沒有任何輸入,因此它是NFA,它有epsilon移動,因此它是epsilon-NFA,而不是DFA .. –

+0

感謝您的澄清 – liwing

2

DFA必須有一個明確的輸入符號從一個國家轉移到另一個國家。在DFA中不允許Epsilon移動,因爲它會將DFA更改爲NFA。例如,假設您處於狀態Q1,並且您有一個轉換(Q1,e)= Q2,在這種情況下,您可以直接轉到Q2而無需應用任何輸入,或者您可以保持Q1狀態,因此您有兩個選擇機會在狀態Q1。如果是DFA,則不得有任何選擇標準。這就是爲什麼DFA沒有epsilon動作。

2

從DFA的定義中,「確定性有限自動機是不能在其他狀態移動沒有得到任何輸入的機器」。而由於小量裝置nothing.Hence DFA不能在小量移動移動。

鑑於從NFA的定義中,「非確定性有限自動機是可以在其它狀態移動沒有得到任何輸入的機器」。所以NFA可以小量移動移動。