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

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

2014-03-30 bulbasaur

你不能總是將CFG轉換爲DFA，但是如果它是左線或右線，那麼你可以。在這種情況下，這個答案可能會有所幫助[左線性和右線性文法]（http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars/13945932#13945932） –

等等對於A-> a B c，我們不能構建一個dfa？ – bulbasaur

看到正確的方法，它首先將語法轉換爲左劃線或右劃線，然後繪製DFA。如果無法將CFG轉換爲左線性（右劃線），那麼實際上語法生成的CFL是常規語言的超集，CFL的DFA是不可能的。 'A - > a B c'只有一個生產規則（不是語法），所以你的queston沒有意義 –

首先，您應該將您的語言轉換爲CNF (Chomskey Normal Form)。然後轉換步驟是這樣：

轉換爲左/右語法被稱爲正規文法。
Convert the Regular Grammar into Finite Automata 用於自動機的轉換如下對於每一個生產甲獲得 - > AB使δ（A，A）= B即作出是「一」從A到B 對於每一個產生標記的A - > a使δ（A，a）=最終狀態。對於每個生產A→ε，使δ（A，ε）= A並且A將是最終狀態。

來源

2015-06-14 23:30:25

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

回答

相關問題