首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
admin
2013-05-11
35
问题
设语言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
软件设计师上午基础知识考试
软考中级
相关试题推荐
数字签名不能保证的是(42)。
X.25网络的数据链路层使用LAPB的协议标准。在扩展模式下,该协议标准允许在收到应答前连续发送(26)帧数据。
如果帧中继网沿着帧传送方向出现了拥塞,则把帧地址字段中的FECN位设置为1,这样接收方就可通过(29)协议要求发送方降低数据速率。
FrameRelayissimplifiedformof(71),similarinprincipleto(72),inwhichsynchronous,framesofdataareroutedtodifferent
下列选项中,不采用虚电路通信的网络是____________网。
采用10Base一5的局域网表示(1)。采用特性阻抗为(2)Ω的粗同轴电缆。这种网络的收发器不在网卡上,而是直接与电缆相连,收发器电缆最长为(3),最大节点数限于(4)个工作站。(4)
以太网介质访问控制策略可以采用不同的监听算法,其中一种是:一旦介质空闲就发送数据,假如介质忙,继续监听,直到介质空闲后立即发送数据,这种算法称为(1)监听算法,该算法的主要特点是(2)。(2011年下半年试题)(1)
防火墙的发展共经历了4个阶段,下列说法错误的是__________。
Calculator is(66)for performing arithmetic operations, but that requires human intervention to alter its stored program, if any
在多个用户共享数据库时,对同一资料的1._____操作可能破坏数据库的2.______。因此数据管理机制要解决丢失更新、不一致以及3.______等问题。解决的方法主要有加锁技术和时标技术。1.____A.连接B.并发C.查
随机试题
锉削内圆弧面时,锉刀除向前运动外,锉刀本身还要()。
公文的发文者和收文者可以是某个领导者个人。
自然环境中的服饰文化有()
防护镜、防护面罩的作用及注意事项?
下列关于气的叙述不正确的是
腹膜炎患者1个月来常出现畏寒、发热,B型超声波检查提示盆腔3cmx4cm液性暗区。下列各项临床表现中对诊断最为重要的是
《机电产品国际招标投标实施办法》中规定,在评标结束后,招标机构应当在招标网进行评标结果公示,公示期为()门
价值工程研究对象的功能量化方法有()。
Mostofusfindtheforgettingeasier,butmaybeweshouldworkontheforgivingpart."Holdingontohurtsandnursinggrudges
OurculturehascausedmostAmericanstoassumenotonlythatourlanguageisuniversalbutthatthegesturesweuseareunderst
最新回复
(
0
)