问CFG语法定义

EN

这听起来像是家庭作业，所以我只给出一些提示。

如何在上下文无关文法产生式中匹配a和c的数量？

您可以使用什么类型的产生式来生成一个b序列？

如何将这两个子问题合并为一个上下文无关文法？

考虑生成语言的上下文无关文法

L1 = {a^nc^n : n >= 0}

比如

G1 = <{S},{a,c},S,{S -> aSc,S-> λ}>

G1中的派生可以描述如下：

G1 =>1 S        (via S)
   =>* a^nSc^n  (via n >= 0 applications of S -> aSc)
   =>1 a^nc^n   (via S -> λ)

语法G1在语言L1中建立a和c的数量和位置之间的所需关系，然后以规则S -> λ的应用而终止。

考虑如何通过应用规则S -> λ来终止G1中的派生，以及如何生成m >= 0 b的序列而不是空字符串。

G2 = <V,N,S2,P>

为了在由相等数量的a和c包围的L2中生成字符串，可以如下扩充G1的规则以获得语法G1'

G1' = <{S} ∪ V,{a,c} ∪ N,S,{S -> aSc,S -> S2} ∪ {P}>

为了解决您的问题，让L2作为语言{b}*，使用G2作为生成它的常规语法。