0

你能解释一下，我如何检查第一个上下文无关语法（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

自动方式是首选。

另外，我如何检查两个任意 上下文无关语法的语言是否相等。

4

2 回答 2

1

一些对于更广泛的语法类别无法判定的问题对于上下文无关语法变得可判定

语言平等是在 cs 中打开且不可判定的问题之一。

但在这种情况下，您实际上可以将 G1' 构建为Sheila Greibach 的 Greinbach 范式，

那么您可以通过在 G1' 上使用 SUBSTITUTION（以更改变体名称）来证明 L(G2)=L(G1') 并获得 G2 语法。

于 2016-01-31T02:06:49.473 回答
0

你实际上不能。这是无法确定的。

你可以证明确定一个文法是否生成 Σ* 的问题是不可判定的。这意味着无法确定测试两种语法是否产生相同的语言，因为您可以为 Σ* 构建一个语法并测试另一个语法是否生成相同的语言然后让您测试一个语法是否具有语言 Σ*，我们知道我们做不到。因此，您也无法测试一种语法的语言是否是另一种语法的语言的子集，因为如果可以，您可以测试 Σ* 是否是该语法的语言的子集，然后会告诉您该语法是否可以生成所有字符串。

对于那个很抱歉！

于 2016-01-31T00:32:37.577 回答