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

Question

已知文法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}

Answer 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|m1}；根据B的规则B→bB|ε知道，由B产生的终结字符串是{bn|0}。因此，L(G1)={dambn|m1，n0}。