你能解释一下，我怎么检查，第一个无上下文语法（G1）的语言是第二个无上下文语法（G2）语言的一个子集 .
G1和G2是两个具有相同字母的LL（1）语法：
{a, b, c, d, f}
制作规则如下：
A -> αB
要么
A -> α
α是非ε串（终端符号） .
无上下文语法G1：
S1 -> aK
K -> bC|cE
C -> cB|d
E -> bA|f
A -> abC
B -> acE
上下文无关语法G2：
S2 -> aX
X -> bZ|cY
Z -> cV|d
Y -> bU|f
V -> aQ
U -> aP
Q -> cY
P -> bZ
Automatic way is preferred.
另外，如何检查两个任意无上下文语法的语言是否相等 .
2 回答
你实际上不能 . 这是不可判定的 .
您可以证明确定语法是否生成Σ的问题是不可判定的 . 这意味着测试两个语法是否产生相同的语言是不可判定的，因为你可以为Σ构建一个语法并测试另一个语法是否生成相同的语言然后让你测试一个语法是否有语言Σ*，我们知道我们做不到 . 因此，您也无法测试一种语法的语言是否是另一种语法语言的子集，因为如果可以，您可以测试Σ*是否是该语法语言的子集，然后会告诉您语法是否可以生成所有字符串 .
对于那个很抱歉！
Some questions that are undecidable for wider classes of grammars become decidable for context-free grammars
语言平等是用cs开放而不是可判定的问题之一 .
但在这种情况下，您实际上可以将G1'构建为Greinbach normal form by Sheila Greibach，
那么你可以通过在G1'上使用SUBSTITUTION（为了改变Variants名称）来证明L（G2）= L（G1'）并获得完全G2语法 .