构造CFG

Question

我真的找不到答案：

L= {vw v元素{a，b)，w元素{b，c}，a's的<=数n}

V-> aV _ bV _e

W-> bW _ cW _e

但我想不出如何把v和w这两个词的结构相互结合起来，并牢记这一限制。有谁能帮我吗？

Answer 1

正如我在“答案”tips for writing cfg中所解释的，正确的方法是首先理解语言中所有可能的字符串模式，然后编写规则。

这个L语言是什么？在L语言串中：

1. All 'a's先于任何'c'

2.数'a'小于或等于'c'数，因此在L的语法中，如果产生规则添加了一个符号'a'，那么它还必须添加一个或多个'c'。

3.对符号'b'的出现没有限制，它可以在任何地方出现任意次数。4.空(null)字符串也属于L，如果'c'== 0，则为'a' = number的编号。出于同样的原因，只有符号'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 ^