context-free-grammar - 构建 CFG

Question

我真的找不到这个问题的答案：

L = {大众 | {a,b) 的 v 元素，{b,c} 的 w 元素，a的数量 <= c 的数量}

V --> aV | BV | e

W --> bW | CW | e

但是我想不出如何将单词 v 和 w 一个接一个地组合起来，并牢记上述限制。谁能帮我一把？

Answer 1

正如我在编写 cfg 的答案提示中解释的那样，正确的方法是首先了解语言中所有可能的字符串模式，然后编写规则。

这是什么语言L？在语言 L 的字符串中：

1. 所有'a's 在任何'c's之前
2. 个数'a'小于或等于个数'c'，所以在 L 的语法中，如果一个产生式规则添加一个符号'a'，那么它也必须添加一个或多个'c'。
3. 符号出现次数没有限制'b'，可以在任何地方出现任意次数。 4.空（null）字符串也属于 L，因为 number of 'a'= number 如果'c'== 0。出于同样的原因，仅由符号组成的字符串'b'也是可以接受的。
5.任何不'a'属于 L 的字符串（也(c + b)*就是 L 的子集）。

现在编写语法规则很容易（阅读注释以了解每个生产规则）：

S →  BaBSBCB | ^    // add `a` add `C` also, B can be any where so added B   
Z →  CZ | BZ | ^    // to create `(c + b)*`
C →  cC | c         // C always generates one or more `c`s  
B →  bB | ^         // there is no restriction on B it generates `b`s or ^