context-free-grammar - 来自上下文无关语言的正式上下文无关语法

Question

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

{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

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

Answer 1

语言 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 } .

在 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在anEbn的图案中，然后将这种感性的 from 转换为句子形式 E必须替换为 B或 A这导致以这样的形式生成一个字符串 ai bj与 i != j , 使用变量 X任意数量 c可以在模式后缀ai bj .

要理解此语法，请阅读: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 = {ai bj ck | i != j or j != k} .