2. 计算机
  3. 设语言L={w|w∈{a,b}+且w中a和b的个数相等}，产生语言L的上下文无关文法是(28)。

设语言L={w|w∈{a,b}+且w中a和b的个数相等}，产生语言L的上下文无关文法是(28)。

admin2013-05-11  49
问题 设语言L={w|w∈{a,b}+且w中a和b的个数相等}，产生语言L的上下文无关文法是(28)。
选项 A、Ga=(VT={a,b}，VN={S，A，B}，S,P)，其中P为，　　　　S→a|aA|bSS　　　　A→aB|bS　　　　B→b|bA|aBB
B、Gb=(VT={a,b}，VN={S,A,B}，S,P)，其中P为，　　　　S→b|bB|aSS　　　　B→aS|bA　　　　A→a|aB|bAA
C、Gc=(VT={a,b}，VN{S,A,B}，S,P)，其中P为，　　　　S→aB|bA　　　　A→a|aS|bAA　　　　B→b|bS|aBB
D、Gd=(VT={a,b}，VN={S，A，B}，S,P)，其中P为，　　　　S→aB|bA|s　　　　A→aS|bAA　　　　B→bS|aBB
答案C
解析 字母表{a,b}上的任何非空串，从其所含a和b的个数来划分，分成下面3个集合：
   ① a和b的个数相等：
   ② a比b的个数多，但仅要a比b的个数多1个的那些子串；
   ③ b比a的个数多，但仅要b比a的个数多1个的那些子串。
   通过上面的分析，根据用文法规则产生句子的原理，设3个非终结符号，不妨称做S、 A、B，它们的产生式分别完成：
   ① 用S的产生式推导出a和b的个数相等的串；
   ② 用A的产生式推导出a比b的个数多1个的串；
   ③ 用B的产生式推导出b比a的个数多1个的串。
   根据3个非终结符号S、A、B的含义，显然，关于S的产生式应该是S→aB|bA。对于A产生的串，若第1个字符是a，则剩下的是a和b的个数相等的串：若第1个字符是 b，则跟随b的是a比b的个数多2个的串，这个串是两个a比b的个数多1个的子串。根据上述分析，写出关于A的产生式A→a|aS|bAA。可以通过和A类似的分析，写出关于 B的产生式B→b|bS|aBB。
   可以用归纳法证明上面所写的文法是正确的。
   现在，我们很清楚被选答案中的4个文法所描述的语言，它们分别是：
   L(Ga)={w|w∈{a,b}+且w中a比b的个数多一个}
   L(Gb)={w|w∈{a,b}+且w中b比a的个数多一个}
   L(Gc)={w|w∈{a,b}+且w中a和b的个数相等}
   L(Gd)={w|w∈{a,b}+且w中a和b的个数相等}
转载请注明原文地址:https://www.kaotiyun.com/show/ybRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

相关试题推荐
随机试题
最新回复(0)