定义生成语言的 CFG(上下文无关语言):
L={a^nb^mc^n | n,m>=0}
谁能告诉我如何解决这个问题?
我的理解是 L 由以下元素组成:{ aabbbcc }(我假设 n=2 和 m=3)
提前感谢约阿希姆
定义生成语言的 CFG(上下文无关语言):
L={a^nb^mc^n | n,m>=0}
谁能告诉我如何解决这个问题?
我的理解是 L 由以下元素组成:{ aabbbcc }(我假设 n=2 和 m=3)
提前感谢约阿希姆
这听起来像家庭作业,所以我只给出一些提示。
在上下文无关的语法产生中,你如何使 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 -> λ)
语法在语言中's 和'sG1
的数量和位置之间建立所需的关系,然后以应用规则结束。a
c
L1
S -> λ
G1
考虑如何通过应用 rule 来终止派生S -> λ
,以及如何生成m >= 0
b
's 序列而不是空字符串。这是一个稍微更普遍的问题的解决方案。假设我们有一种L2
由语法生成的语言
G2 = <V,N,S2,P>
为了生成由相等数量的' 和'L2
包围的字符串,可以将的规则扩充如下以获得语法:a
c
G1
G1'
G1' = <{S} ∪ V,{a,c} ∪ N,S,{S -> aSc,S -> S2} ∪ {P}>
为了解决您的问题,让我们成为生成它L2
的语言{b}*
和常规语法。G2