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
查看答案
正确答案
试题解析
解析:字母表{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的个数相等}