A-A+

已知文法G1=(VT={a b d} VN={S A B} S P) 其中P为 S→dAB

2022-08-06 05:43:04 问答库 阅读 176 次

问题详情

已知文法G1=(VT={a,b,d},VN={S,A,B},S,P),其中P为, S→dAB A→aA|a B→bB|ε 该文法生成的语言是(28)。
A.{dambn|m≥0,n≥O}
B.{dambn|m≥1,n≥0}
C.{dambn|m≥0,n≥1}
D.{dambn|m≥1,n≥1}请帮忙给出正确答案和分析,谢谢!

参考答案

正确答案:B
解析:已知文法G=(VT,VN,S,P),它所产生的语言定义如下:若有S(11)w,则称w是文法G的一个句型。仅含终结符的句型是一个句子。语言L(G)是由文法G产生的所有句子组成的集合:L(G)={w|Sw且w∈VT*}推导的定义如下:设文法G=(VT,VN,S,P),A→β∈P,γ,δ∈V*,则稀γAδ直接推导出γβδ,表示成这个定义告诉我们,若知道γAδ∈V*,根据A→β∈,可求出γβδ∈V*,方法是用A→β的右部β替换γAδ中的A得到γβδ;相反,若知道γβδ∈V*,根据A→β∈P,可求出γAδ∈V*,方法是用A→p的左部A替换γβδ中的β得到γAδ。若存在一个推导序列:,则称从a0经n步推导出an,表示成根据文法G1的第1条规则S→dAB知道,文法G1产生的句子的第1个字符是d,后跟着由A产生的终结字符串,再后边跟着由B产生的终结字符串。根据文法G1的第2条规则A→aA|a知道,由A产生的终结字符串是{am|m≥1};根据B的规则B→bB|ε知道,由B产生的终结字符串是{bn|≥0}。因此,L(G1)={dambn|m≥1,n≥0}。

考点:文法