所有上下文无关语法都可以转换为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吗？

回答

相关问题