dfa

3熱度

3回答

我搜索谷歌，並在很多頁面中給出了在最小化DFA死亡狀態或陷阱狀態被刪除。我的問題是，如果某些轉換未定義，它又如何成爲DFA。那麼你說的人呢？

2熱度

2回答

我一直在努力與這一段時間，我不能拿出任何東西。任何指針將非常感激。問題是：鑑於所有隻接收均勻長度字的DFA的語言，證明它是否在P中。我已經考慮過製作一個圖靈機器，它可以像BFS/Dijkstra算法那樣遍歷給定的DFA，以便找到從開始狀態到接受狀態的所有路徑，但不知道如何處理循環？謝謝！

8熱度

1回答

正則表達式會生成具有死亡或多餘狀態的DFA

我正在尋求在詞法分析器中實現DFA最小化，但似乎無法生成看起來不像它已經是最小DFA的DFA表達。我正在構建使用thomson構建從後綴正則表達式構建的NFA中的DFA。它幾乎與龍書中描述的完全一致。爲了使詞法分析器中的幾個NFA能夠使用來自開始狀態的ε轉換進行組合。正是在這個組合的NFA中應用了DFA算法。那麼，是否有任何「已知」的正則表達式會產生一個DFA，這將成爲死亡狀態消除和狀態最小化

0熱度

2回答

常規語言永遠是無限的

我有點困惑於常規語言的概念。由於所有常規語言都可以被dfa接受，並且dfa始終包含循環。所以看起來dfa可以容納無數的字符串。這是否意味着所有正規語言都是無限的？什麼是空集。這是一種常規語言嗎？

-1熱度

1回答

爲什麼語言不正常？

顯示語言不正常。 L = {a^n b^m：n> m}

4熱度

2回答

如何判斷正則表達式實現是否使用DFA或NFA？

我面臨的問題是，某個regex implementation是基於DFA還是NFA。我明白這一點的出發點是什麼。也可以問：我在找什麼？什麼是基本模式和/或特徵？一個很好的解釋性鏈接或者一點比較（即使不直接用於正則表達式）也是非常好的。

0熱度

1回答

你如何證明這個抽象引理的例子？

我在測試中弄錯了這個問題，並想知道是否有人可以解釋它，顯示採取的步驟來得出結論。任何幫助，將不勝感激。在L_neq = {0^i1^j |在給定m狀態DFA的情況下，有人選擇字符串0 ^（m/2）1 ^（m/2 + 1）。然後，他們選擇y = 0，並通過抽水顯示，我們可以到達L_neq之外的串0 ^（m/2 + 1）1 ^（m/2 + 1）。這個證明是否正確？爲什麼或者爲什麼不？此外，如果證明

0熱度

2回答

DFA和常規語言

我一直在考慮以下內容，我認爲答案是肯定的。確實，DFA可接受的常規語言的每個子集都是DFA可接受的嗎？

0熱度

1回答

DFA中具有'1'作爲第5個符號的狀態的最小數量

DFA接受右側具有'1'作爲第5個符號的字符串所需的狀態的最小數量是多少？字符串定義在字母{0,1}上。

0熱度

1回答

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

（ABûAABüABA）* 我做到了，但我想它的正確性一些反饋：如果它是正確的：我們可以簡化（ABûAABüABA）*任何進一步？如果不是：我錯過了什麼？編輯：我似乎缺少從所有3個最終狀態回到初始狀態的電子轉換，我需要一個新的狀態，它是初始和最終將轉到電子轉換的舊初始狀態。（Kleene Star規則）。附：我們是否也可以簡化(a u b)*aabab和(a u b)*a(a u b)(