dfa

0熱度

1回答

對於Σ= {a，b，c，d，e，...，z}，考慮單詞w的集合L，使得w的最後一個符號沒有出現過。例如，蘋果，谷歌，k和ε這兩個詞在L中，但馬鈴薯和營養詞不在L.假設我們要爲這種語言構建一個DFA。它會有多少個州（最低限度）？簡潔地描述DFA：不要嘗試繪製它，而是使用合適的數學符號解釋它的形式定義（例如狀態和轉換）。我不需要整個定義，只是一個開始，它會有多少個狀態以及爲什麼。從那裏我很聰明，我可

0熱度

1回答

所有最終狀態都可以從DFA的起始狀態中獲得嗎？

假設DFA D是有效的DFA。這意味着從初始狀態到最終狀態的可達性是什麼？我可以假設這樣的： $ \三角洲^ *（Q_0，W）= F $，其中$ W \中\西格瑪$和$ F \在F $

4熱度

1回答

如何在設計NFA時直觀地思考如何設計NFA

我不知道這個問題是否適合被問到，但我絕對認爲它應該被問到。當然，我確實看到了很多很好的和內容豐富的問題，關於互聯網和StackOverflow本身的文章。但我發現所有問題或文章都遵循特定的規則或模式來解釋該主題。我的意思是，當在NFA，DFA或正則表達式中提出問題時，遵循這些主題的定理/規則（計算理論）提出了一個解決方案。 But what I feel is that, as most of

1熱度

1回答

使用kleene star從正則表達式構造DFA時存在歧義

如何避免從正則表達式（如[ab]*ab）直接構造DFA時出現歧義？在一個簡單的實現中，[ab]*的循環轉換吃掉了所有a或b，它當然不同於現有的正則表達式實現，它們最終也考慮到「ab」。因此，執行自動機必須知道何時從第一個轉換週期跳轉到最後兩個轉換「a到b」。任何想法如何實現這一目標？我對直接DFA構建的答案感興趣，而不是轉換爲DFA的NFA。 Adrian McCarthy's answer

2熱度

1回答

自動機理論：將上下文無關語法轉換爲DFA

如何將無上下文語法轉換爲DFA？這很容易，如果我們有如 A-> a B的轉換。但是當我們將轉換作爲A-> a B c時。那麼我們應該如何將它表示爲DFA

0熱度

1回答

NFA轉化爲DFA =確定性？

我在決定論和非決定論的意義上掙扎了一下。當涉及到自動機時，我得到了不同，但我似乎無法找到以下答案：NFA轉換爲DFA轉換是否具有確定性？如果可以爲同一常規語言構建多個DFA，那麼這是否意味着NFA轉換爲DFA的結果不是唯一的？因此一個非確定性算法？我很高興你可以提供任何信息。在此先感謝！

2熱度

1回答

沒有最終狀態的DFA

我們可以有沒有最終狀態的Deterministic Finite Automata (DFA)。是否意味着！沒有最終狀態的Deterministic Finite Automata (DFA)是什麼意思？謝謝

0熱度

1回答

直接從正則表達式的時間複雜度DFA構造

我想直接使用龍書中的algo 3.36從正則表達式中瞭解DFA構造的時間複雜度。我很困惑外循環將執行多少次？正如在算法中提到的Dstates，它們是否等於正則表達式中的操作數？還有多少工作將在內完成循環執行等於|Σ|次？謝謝。

1熱度

1回答

從初始狀態開始返回DFA中的所有可達狀態

我試圖在Haskell中編寫一個程序，該程序返回從初始狀態開始的可達狀態列表，類似於深度優先搜索。 states_reachable :: Eq st => DFA st -> [st] states_reachable (qs, sigma, delta, s, inF) = [delta q a | q <- qs, a <- sigma] 注：適量是狀態集合西格瑪的是字母

0熱度

1回答

用JAVA ArrayList實現DFA最小化算法

我已經用數組列表實現了DFA minimization algorithm，但是它沒有返回正確的答案。如果有人能指出我失蹤的算法的哪一部分，我將不勝感激（並糾正我是否使用了一種有效的方法來實現它）。該程序應該從文件讀取數據，然後對其進行處理。但是這個功能與這些數據無關。我已經硬編碼它的工作。實現該算法的方法被命名爲（unreachableStates） DEBUG我：所以我就徹底的代碼，並發現