當r和r的DFA被確定時，發現r *的DFA

我想要說明當定義r的r和DFA時，找到r *的DFA的方法的例子。以及如何思考？我讀了一本教科書，但我不明白。謝謝。當r和r的DFA被確定時，發現r *的DFA

2017-09-17 BeginTP

r *是包含來自r的所有串聯0,1,2,3,4，...字符串的語言。所以對r *而言，明顯的FA就是能夠運行D 0,1,2,3,4，...次的DFA，並在這些運行中的任何一個之後接受。從任何接受狀態到開始狀態的lambda/empty轉換將實現1次或多次運行。產生的自動機不再是確定性的。您可以使用標準方法來確定它。這種構造不會將空字符串添加到自動機的語言中。如果它已經存在於r中，這不是必需的。否則，您需要添加一種接受r *的自動機中空字符串的方法，例如使用新的開始狀態。

在消除空過渡方面有一點經驗，您還可以更簡單地構建DFA。

來源

2017-09-17 21:04:57

要小心 - 只要從每個接受狀態向開始狀態添加一個epsilon，就不會*創建一個接受輸入語言的明星的NFA。（我通常會給出一個例子，說明爲什麼在我的理論課程中，這對我的學生來說是失敗的。） – templatetypedef

謝謝@templatetypedef，我在這裏有點倉促，不記得那個。我希望現在的答案更好。 –

這裏還有一個問題。這是一個可行的結構：添加一個可接受的新開始狀態。添加一個從它到舊開始狀態的epsilon轉換，並將每個舊接受狀態的epsilons添加到新的開始狀態。 – templatetypedef

當r和r的DFA被確定時，發現r *的DFA

回答

相關問題