8

如何为以下语言生成正式的上下文无关语法：

{ai bjck | i != j or j != k}

我有以下作品，但无法理解：

     S->AX | YC                     unequal b’s c’s or a’s b’s

     A-> aA | e                     0 or more A’s

     C -> cC |e                     0 or more c’s

     B -> bB | e                    0 or more B’s

     X -> bXc | bB | cC             equal b’s, c’s then 1+ b’s, 
                                    1+C’s (i.e. unequal b’s and c’s)

     Y -> aYb | bB | aA             unequal a’s b’s

谁能帮我理解和解决这个问题？

4

1 回答 1

14

该语言 可以简单地写成和。 L = {ai bj ck | i != j or j != k} L = L1 U L2 L1 = {ai bj ck | i != j } L1 = {ai bj ck | j != k }

在 L 1中，对符号没有限制，c只有条件numberOf(a)不应该等于numberOf(b)。>或<。numberof(a) _ . 所以这种语言的语法应该是： numberOf(b) numberof(a) numberOf(b)

L1  =>  EX              // L1 is start variable 
E  =>  aEb | A | B
X  =>  C | ^ 
A  =>  aA | a
B  =>  bB | b
C  =>  cC | c

在上面使用 E 的语法中，我们可以生成相同数量的a和b的模式，然后将这种感性的 from 转换为句子形式，要么必须替换为，要么生成一个形式为这样的字符串，使用，使用任意数量的变量都可以后缀为模式。anEbnEBAai bji != jXcai bj

要理解这个语法，请阅读：创建上下文无关语法的技巧和为什么需要终端？我的解决方案是否足够？

类似地，对于 L 2没有对符号的限制，a只有条件numberOf(b)不应该等于numberOf(c)。>或<。numberof(b) _ . 所以这种语言的语法应该是： numberOf(c) numberof(b) numberOf(c)

L2  =>  YF              // L2 is start variable 
F  =>  bFc | B | C
Y  =>  A | ^ 
A  =>  aA | a
B  =>  bB | b
C  =>  cC | c

现在使用这两个语法并引入一个新的开始变量S和两个新的生产规则S => L1 | L2，我们得到 language 的语法。 L = {ai bj ck | i != j or j != k}

于 2013-10-20T07:39:19.810 回答