首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
admin
2013-05-11
45
问题
设语言L={w|w∈{a,b}
+
且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
选项
A、G
a
=(V
T
={a,b},V
N
={S,A,B},S,P),其中P为, S→a|aA|bSS A→aB|bS B→b|bA|aBB
B、G
b
=(V
T
={a,b},V
N
={S,A,B},S,P),其中P为, S→b|bB|aSS B→aS|bA A→a|aB|bAA
C、G
c
=(V
T
={a,b},V
N
{S,A,B},S,P),其中P为, S→aB|bA A→a|aS|bAA B→b|bS|aBB
D、G
d
=(V
T
={a,b},V
N
={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(G
a
)={w|w∈{a,b}
+
且w中a比b的个数多一个}
L(G
b
)={w|w∈{a,b}
+
且w中b比a的个数多一个}
L(G
c
)={w|w∈{a,b}
+
且w中a和b的个数相等}
L(G
d
)={w|w∈{a,b}
+
且w中a和b的个数相等}
转载请注明原文地址:https://kaotiyun.com/show/ybRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
为两个对等的开放系统之间提供按“请求/应答”方式交换管理信息的协议是(65)。
如果帧中继网沿着帧传送方向出现了拥塞,则把帧地址字段中的FECN位设置为1,这样接收方就可通过(29)协议要求发送方降低数据速率。
Inter公司用于网络处理的IXP系统微处理器支持DDR内存接口。在200MHz外频条件下,DDR内存带宽可达(3)。
计算机网络中的主机和申请资源的终端构成(33)。
通信系统的目的是在通信双方之间交换数据,对于构成通信模型的5大要点分别是信源、发送器、传输系统、接收器、(57)。
RIP协议中可以使用多种方法防止路由循环,在以下选项中不属于这些方法的是______。
下面ACL语句中,表达“禁止外网和内网之间互相ping”的是(41)。
报文摘要算法MD5的输出是(1)位,SHA-1的输出是(2)位。(2010年下半年试题)(2)
WLANsareincreasinglypopularbecausetheyenablecost—effectiveconnectionsamongpeopleandapplicationsthatwerenotpossib
内存按字节编址,地址从90000H~CFFFFH,若用存储容量为16Kx8bit的存储器芯片构成该内存,至少需要__________片。
随机试题
A.发作性眩晕、耳鸣、听力减弱B.伴鼓膜穿孔C.渐进性眩晕、耳鸣、听力减退、口周麻木D.头部处在一定位置时眩晕E.上感后眩晕、恶心、呕吐、无耳鸣及听力减退上述临床表现符合哪种疾病内耳药物中毒
A、CMB、LDLC、VLDLD、HDLE、IDL体内主要运输外源性甘油三酯的是
葡萄球菌肺炎抗生素治疗的疗程是
单室模型多剂量静脉注射给药稳态最大血药浓度公式是()。
商业汇票的承兑期限最长不超过()。
该公司2003年的资产净利率为()。该公司2003年的应收账款周转率为()次。
依据新的《企业所得税法》,下列适用20%比例税率的是( )。
以下是一个教学片断,找出其中所运用的教学原则。教师:讲课之前,同学们请先告诉我,我手里现在拿的是什么?学生:土豆/马铃薯。教师:对,同学们都很熟悉,也很常见,而且也有不少人喜欢吃吧。那么,马铃薯的发源地是在中国吗?学
阅读下列材料并回答问题材料12004年4月26日,中国国务院新闻办发表《中国的就业状况和政策》白皮书。白皮书指出,中国有近13亿人口,是世界上人口最多的国家,解决就业问题任务繁重、艰巨、紧迫。白皮书指出,近年来,在就业压力持续加大的情况下,
ICMPisshortforInternet(71)MessageProtocol,andisanintegralpartoftheInternet(72)suite(commonlyreferredtoas
最新回复
(
0
)