所有上下文無關語法都可以轉換爲NFA/DFA嗎？

我已經看到了這個帖子有關如何上下文無關文法轉換爲DFA： Automata theory : Conversion of a Context free grammar to a DFA 所有上下文無關語法都可以轉換爲NFA/DFA嗎？

然而，只是想知道都可以上下文無關文法轉換爲DFA/NFA？那些無法用正則表達式表達的上下文無關文法呢？防爆。 S - >（S）| （）

謝謝！

來源

2016-12-13 ssssay

只有常規語言才能轉換爲DFA，並非所有CFG都代表常規語言，包括問題中的常規語言。

所以答案是「否」。

的NFA並不比DFA的更富有表現力，因此，如果您更換DFA與NFA

一個CFG代表一個普通的語言，如果是左手或線性上述說法仍然是正確的。但僅僅一個CFG不是左線或右線的事實證明什麼都沒有。例如，S→a | a S a碰巧生成與S→a | S a a相同的語言。

來源

2016-12-13 19:17:46 rici

http://hackingoff.com/images/basic-bottom-up-parser/2016-12-13_18-37-59_-0800-dfa.svg剛剛遇到這個，現在有點困惑於LR的DFA（ 0）解析器。 LR（0）語法分析器的DFA是否爲上下文無關語法的轉換？或者它只是幫助構建LR（0）解析器（有多個完成狀態）？ – ssssay

@ssssay：雖然該頁面將其圖形描述爲DFA，但驅動LR語法分析器的實際上是PDA（下推自動機），它不是F（有限）。沒有顯示推送轉換，「接受」狀態實際上是彈出轉換（由於它們依賴於該點的堆棧內容，因此不能繪製圖表）。很容易看出情況是這樣的;您只需嘗試使用該機器實際處理輸入。（並且，並非所有的CFG都是LR（0）甚至LR（k））。 – rici

所有上下文無關語法都可以轉換爲NFA/DFA嗎？

回答

相關問題