我需要一种算法来检查G1的语言是否是G2语言的子集 . （假设G1和G2是两个LL（1）语法，它们具有相同的字母表，其生成规则是A - > aB或A - > a形式，“a”是非epsilon . 我有一个解析算法根据字符串检查语法但不检查另一种语言 . 是否有人有解决方案 .
你的语法看起来像是正常的 . 因此算法是将语法转换为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) )
1 回答
你的语法看起来像是正常的 . 因此算法是将语法转换为NFA . 这是一个简单的1-1映射 . 然后使用子集构造将NFA转换为DFA . 调用这些A和B.很容易分析它们以确定L（A）子集？磅） . 例如，因为有众所周知的有效算法来确定L（A）==？ L（B）并构造一个接受L（A）交点L（B）的新机器I（A，B），只需计算