2

定义生成语言的 CFG(上下文无关语言):

L={a^nb^mc^n | n,m>=0}

谁能告诉我如何解决这个问题?

我的理解是 L 由以下元素组成:{ aabbbcc }(我假设 n=2 和 m=3)

提前感谢约阿希姆

4

2 回答 2

2

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

在上下文无关的语法产生中,你如何使 a 和 c 的数量匹配?

你可以使用什么样的产生式来生成 b 的序列?

这两个子问题如何组合成一个上下文无关文法?

于 2011-06-24T21:26:40.943 回答
0

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

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 -> λ)

语法在语言中's 和'sG1的数量和位置之间建立所需的关系,然后以应用规则结束。acL1S -> λ

G1考虑如何通过应用 rule 来终止派生S -> λ,以及如何生成m >= 0 b's 序列而不是空字符串。这是一个稍微更普遍的问题的解决方案。假设我们有一种L2由语法生成的语言

G2 = <V,N,S2,P>

为了生成由相等数量的' 和'L2包围的字符串,可以将的规则扩充如下以获得语法:acG1G1'

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

为了解决您的问题,让我们成为生成它L2的语言{b}*和常规语法。G2

于 2011-06-25T17:30:39.500 回答