我看过这篇关于如何将上下文无关语法转换为 DFA 的文章: Automata theory : Conversion of a Context free grammar to a DFA
但是，只是想知道所有上下文无关语法都可以转换为 DFA/NFA 吗？无法表达为正则表达式的上下文无关语法又如何呢？前任。 S->(S)| ()
谢谢!
最佳答案
只有常规语言可以转换为 DFA，并且并非所有 CFG 都代表常规语言，包括问题中的语言。
所以答案是“不”。
NFA 并不比 DFA 更具表现力，因此如果将 DFA 替换为 NFA，上述陈述仍然成立
如果 CFG 是右线性或左线性的，则表示它是正则语言。但 CFG 不是左线性或右线性这一事实并不能证明什么。例如，S→a | a S a 恰好生成与 S→a | 相同的语言S a a.
关于parsing - 所有上下文无关语法都可以转换为 NFA/DFA 吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41128425/