首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
admin
2013-05-11
41
问题
设语言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)。
IIS安装的硬盘分区最好选用NTFS格式,这是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加
从信息资源管理的观点出发,信息系统的逻辑结构一般由4部分组成,其中(18)利用信息系统提供的信息进行决策和选择,是信息系统服务的对象。
ISO9000系列标准和软件成熟度模型(CMM)都着眼于质量和过程管理。ISO9000系列标准强调质量管理必须坚持进行(9)。
ThedefactostandardApplicationProgramInterface(API)forTCP/IPapplicationsisthet•sockets”interface.AlthoughthisAPlwa
某实验室使用无线路由器提供内部上网,无线路由器采用固定IP地址连接至校园网,实验室用户使用一段时间后,不定期出现不能访问互联网的现象,经测试无线路由器工作正常,同时有线接入的用户可以访问互联网。分析以上情况,导致这一故障产生的最可能的原因是(50)。
(1)是面向对象程序设计语言不同于其他语言的主要特点,是否建立了丰富的(2)是衡量一个面向对象程序设计语言成熟与否的重要标志之一。(1)
下一代IP协议IPv6的基本报头包含(203)个字节,并包含多个可扩展报头。基本报头中的(204)字段指明了一个特定的源站向一个特定目标站发送的分组序列。一个数据流由(205)命名。在IPv6中,地址被扩充为128位。按照IPv6的地址表示方法,以下地址中
请用120字以内文字,从业务的继承性、升级成本(时间、工作量)和扩展性三个方面简要说明开发人员所提方案的优点。WebService的三个基本技术是WSDL、SOAP、UDDI,它们都是以XML为基础定义的。请用120字以内文字,简要说明WSDL、SO
Calculator is(66)for performing arithmetic operations, but that requires human intervention to alter its stored program, if any
随机试题
(2013年4月,2010年10月,2009年10月,2009年4月)1956年,陈云在中共八大上提出了________的思想。
Conversationbeginsalmostthemomentwecomeintocontactwithanotherandcontinuesthroughouttheday【C1】______theaidofcel
Yettheseglobaltrendshidestarklydifferentnationalandregionalstories.VittorioColao,thebossofVodafone,whichoperat
为得到高信噪比的图像,应选择
健康是身体上、_______和_______的完好状态,而不仅是没有疾病和虚弱。
下列对疾病定义的描述中,不正确的是
A.罚款B.责令改正C.通报批评D.吊销执业证书E.暂停执业活动医师判断患者为非正常死亡但未按照规定报告,应给予的行政处罚是()
属于物业管理企业运行机制的是()。
在企业中,出于内源性动机的员工着重的是( )。
Thispassagegivesageneraldescriptionofwhyrecessionsoccurandhowtheymakeacountry’seconomyworse.Thevalueofgood
最新回复
(
0
)