如何检查一种上下文无关文法的语言是第二种上下文无关文法的子集？
How can I check that the language of one context-free grammar is a subset of a second context-free grammar?
你能解释一下吗，我如何检查第一个上下文无关语法 (G1) 的语言是第二个上下文无关语法 (G2) 的语言的子集。
G1 和 G2 是两个具有相同字母表的 LL(1) 文法：
{a, b, c, d, f}
生产规则如下：
A -> αB
或
A -> α
并且 α 是非 epsilon 字符串（终端符号）。
上下文无关语法 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
首选自动方式
In additional, how can I check that the languages of two arbitrary
context-free grammars are equal.
你实际上不能。无法判定。
你可以证明判断文法是否生成 Σ* 的问题是不可判定的。这意味着测试两个文法是否产生相同的语言是不可判定的，因为你可以为 Σ* 构建一个文法并测试另一个文法是否产生相同的语言然后让你测试一个文法是否有语言 Σ*，我们知道我们做不到。因此，您也无法测试一种语法的语言是否是另一种语法语言的子集，因为如果可以的话，您可以测试 Σ* 是否是该语法语言的子集，然后它会告诉您该语法是否可以生成所有字符串。
对此感到抱歉！
语言平等是cs中开放的问题之一，不可判定..
但在这种情况下，您实际上可以将 G1' 构建为 Greinbach normal form by Sheila Greibach,
那么你可以证明L(G2)=L(G1')
通过在 G1' 上使用 SUBSTITUTION（以更改变体名称）并准确获得 G2 语法。
你能解释一下吗，我如何检查第一个上下文无关语法 (G1) 的语言是第二个上下文无关语法 (G2) 的语言的子集。
G1 和 G2 是两个具有相同字母表的 LL(1) 文法：
{a, b, c, d, f}
生产规则如下：
A -> αB
或
A -> α
并且 α 是非 epsilon 字符串（终端符号）。
上下文无关语法 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
首选自动方式
In additional, how can I check that the languages of two arbitrary context-free grammars are equal.
你实际上不能。无法判定。
你可以证明判断文法是否生成 Σ* 的问题是不可判定的。这意味着测试两个文法是否产生相同的语言是不可判定的，因为你可以为 Σ* 构建一个文法并测试另一个文法是否产生相同的语言然后让你测试一个文法是否有语言 Σ*，我们知道我们做不到。因此，您也无法测试一种语法的语言是否是另一种语法语言的子集，因为如果可以的话，您可以测试 Σ* 是否是该语法语言的子集，然后它会告诉您该语法是否可以生成所有字符串。
对此感到抱歉！
语言平等是cs中开放的问题之一，不可判定..
但在这种情况下，您实际上可以将 G1' 构建为 Greinbach normal form by Sheila Greibach,
那么你可以证明L(G2)=L(G1') 通过在 G1' 上使用 SUBSTITUTION（以更改变体名称）并准确获得 G2 语法。