是否所有上下文无关语法都可以转换为NFA/DFA？
Can all context free grammars be converted to NFA/DFA?
我看过这个 post 关于如何将上下文无关语法转换为 DFA 的内容：
Automata theory : Conversion of a Context free grammar to a DFA
但是，只是想知道是否可以将所有上下文无关文法都转换为DFA/NFA？不能用正则表达式表达的上下文无关文法呢？前任。 S->(S) | ()
谢谢！
只有常规语言可以转换为 DFA，并非所有 CFG 都代表常规语言，包括问题中的语言。
所以答案是"no"。
NFA 并不比 DFA 更具表现力，因此如果您将 DFA 替换为 NFA，上述说法仍然成立
如果 CFG 是右线性或左线性的，则 CFG 表示常规语言。但是 CFG 不是左线性或右线性这一事实并不能证明什么。例如，S→a | a S a 恰好生成与 S→a | S a a.
相同的语言
我看过这个 post 关于如何将上下文无关语法转换为 DFA 的内容： Automata theory : Conversion of a Context free grammar to a DFA
但是，只是想知道是否可以将所有上下文无关文法都转换为DFA/NFA？不能用正则表达式表达的上下文无关文法呢？前任。 S->(S) | ()
谢谢！
只有常规语言可以转换为 DFA，并非所有 CFG 都代表常规语言，包括问题中的语言。
所以答案是"no"。
NFA 并不比 DFA 更具表现力，因此如果您将 DFA 替换为 NFA，上述说法仍然成立
如果 CFG 是右线性或左线性的，则 CFG 表示常规语言。但是 CFG 不是左线性或右线性这一事实并不能证明什么。例如，S→a | a S a 恰好生成与 S→a | S a a.