等效的上下文无关文法
Equivalent Context-Free Grammars
当两个不同的上下文无关文法在结构上等效（在非常基本的水平上）时，我无法理解和指出。在确定两个 CFG 是否 等价 时，我应该寻找哪些 clues/hints？任何帮助将不胜感激。
判断两个CFG是否等价是一个undecidable problem，所以一般没有好的方法来断言两个CFG是否等价。
你没有说出等价的确切含义 "structurally (at a very basic level)"。
著名的undecidability result 关注也称为弱等价：两个文法等价当且仅当它们生成相同的语言（=词集).
不可判定性意味着不存在解决此问题的每个 实例的通用算法。个别实例可能还是很容易解决的（你大概可以想到例子）。
事实上，有一个很大的子类 弱等价性是可判定的上下文无关语言：确定性上下文无关 语言。不幸的是，在这种情况下存在算法并不意味着该算法是有效的。
但是，如果您所说的结构等价是指 "only renaming nonterminals" 或 "generating parse trees of the same shape"，这可能是 simpler problem。
当两个不同的上下文无关文法在结构上等效（在非常基本的水平上）时，我无法理解和指出。在确定两个 CFG 是否 等价 时，我应该寻找哪些 clues/hints？任何帮助将不胜感激。
判断两个CFG是否等价是一个undecidable problem，所以一般没有好的方法来断言两个CFG是否等价。
你没有说出等价的确切含义 "structurally (at a very basic level)"。
著名的undecidability result 关注也称为弱等价：两个文法等价当且仅当它们生成相同的语言（=词集).
不可判定性意味着不存在解决此问题的每个 实例的通用算法。个别实例可能还是很容易解决的（你大概可以想到例子）。
事实上，有一个很大的子类 弱等价性是可判定的上下文无关语言：确定性上下文无关 语言。不幸的是，在这种情况下存在算法并不意味着该算法是有效的。
但是，如果您所说的结构等价是指 "only renaming nonterminals" 或 "generating parse trees of the same shape"，这可能是 simpler problem。