单选题 对于以下的文法G(S),______是其句子(从S出发开始推导)。
G(S):S→M|(S,M) M→P|MP P→a|b|c|…x|x|z
A.(abc) B.((a,f)) C.(c,(da)) D.((fac,bb)g)

【正确答案】 D
【答案解析】[解析] 对于语言结构的文法表示中的“推导”,就是用产生式的右部替换产生式左部的符号。从文法的开始符号出发,不能推导出(abc)、((a,f))和(c,(da))。
对于产生符号串((fac,bb),g)的最左推导过程如下。
S=>(S,M)=>((S,M),M)=>((M,M),M)=>((MP,M),M)=>((MPP,M),M)=>((PPP,M),M)=>((fPP,M),M)=>((faP,M),M)=>((fac,M),M)=>((fac,MP),M)=>((fac,PP),M)=>((fac,bP),M)=>((fac,bb),M)=>((fac,bb),g)