如何將（ab u aab u aba）*轉換爲NFA？

Question

（ABûAABüABA）*

我做到了，但我想它的正確性一些反饋：

如果它是正確的：我們可以簡化（ABûAABüABA）*任何進一步？

如果不是：我錯過了什麼？

編輯：我似乎缺少從所有3個最終狀態回到初始狀態的電子轉換，我需要一個新的狀態，它是初始和最終將轉到電子轉換的舊初始狀態。 （Kleene Star規則）。

附：我們是否也可以簡化(a u b)*aabab和(a u b)*a(a u b)(a u b)(a u b)(a u b)。

我之所以問，因爲如果沒有辦法簡化/最小化，這將是一個很長的離譜...... DFA

Answer 1

我可以看到你的第一種情況下的小簡化的，你可以把它寫成（a（bu ab u ba））*但這並不一定有幫助。我仍然會猜想，您的DFA不會像您想象的那樣需要很多州。

後面兩種情況都需要32個狀態的DDA來跟蹤最後5個字符的讀取。區別在於第二個DFA只有一個終端狀態，而第三個DFA有16個。