context-free-grammar - 上下文无关语言的形式上下文无关语法

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


{a bc | 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

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

最佳答案

语言 L = {a b c | i != j or j != k}可以简单地写为 L = L U L ，这样 L = {a b c | i != j } 和 L = {a b c | j != k }。

在L1中，对符号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和aEb，然后将这种感伤情绪从句子形式转换为E必须替换为B或A导致以这样的形式生成字符串，即a b和i != j，使用变量X可以将任意数量的c后缀加到模式a b后。

要了解此语法，请阅读：Tips for creating Context free grammar和Why the need for terminals? Is my solution sufficient enough?

类似地，对于L2，对符号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，我们得到语言 L = {a b c | i != j or j != k}的语法。