已知文法G2=(VT={a,b}，VN={S，A}，S,P)，其中P为，　　　　　　　　　　　　　　　　　　S→Sb｜Ab　　　　　　　　　　　　　　　　　　A→aSb｜ε　　　　该文法生成的语言是(28)。

admin2009-02-15 31

问题已知文法G2=(V_T={a,b}，V_N={S，A}，S,P)，其中P为，　　　　　　　　　　　　　　　　　　S→Sb｜Ab　　　　　　　　　　　　　　　　　　A→aSb｜ε　　　　该文法生成的语言是(28)。

选项 A、{a^mbⁿ｜n＞m≥0}
B、{a^mbⁿ｜m＞n≥0}
C、{a^mbⁿ｜n≥m≥1}
D、{a^mbⁿ｜m≥n≥1}

答案A

解析根据文法G2的产生式A→aSb｜ε，用A的产生式推导出终结符号串，如果仅用A→ε，则产生{ε}；如果先用若干次A→aSb推导，再用A→ε，则推导过程如下：

因此，由A生成的终结符号集合是{a^mb^m｜m＞0}。
从S出发使用产生式S→Sb｜Ab进行推导，或者

。
最后，L(G2)={a^mb^m｜m≥0}连接{b^k｜k＞0}={a^mb^m+k｜m+k＞m≥0}={a^mbⁿ｜n＞m≥0}。

转载请注明原文地址:https://kaotiyun.com/show/UkxZ777K

软件设计师上午基础知识考试

相关试题推荐

随机试题

最新回复(0)