0

我需要一个算法来检查 G1 的语言是否是 G2 语言的子集。（假设 G1 和 G2 是两个具有相同字母表的 LL(1) 语法，其产生规则是 A-->aB 或 A-->a 形式，并且“a”是非 epsilon。我有一个解析算法根据字符串检查语法但不检查另一种语言。有没有人有解决方案。

4

1 回答 1

1

你的语法看起来很正常。所以算法是将语法转换为NFA。这是一个简单的 1-1 映射。然后使用子集构造将 NFA 转换为 DFA。将这些称为 A 和 B。分析它们以确定 L(A) 子集很容易吗？磅）。例如，因为有众所周知的有效算法来确定 L(A) ==? L(B) 并构造一个接受 L(A) 交集 L(B) 的新机器 I(A,B)，只需计算

( L(I(A,B)) ==? L(A) )  or  ( L(I(A,B)) ==? L(B) )
于 2015-12-23T17:22:41.017 回答