首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
admin
2013-05-11
42
问题
设语言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
软件设计师上午基础知识考试
软考中级
相关试题推荐
IPv6是下一代IP协议。IPv6的基本报头包含(27)B,此外还可以包含多个扩展报头。基本报头中的(28)字段指明了一个特定的源站向一个特定目标站发送的分组序列,各个路由器要对该分组序列进行特殊的资源分配,以满足应用程序的特殊传输需求。一个数据流由(29
信元是信元交换的单位。为控制差错,在信元中包括CRC校验和,其生成公式为(22),校验和对(23)进行校验。信元交换采用(24)技术进行复用。在交换过程中,当实施VP交换时,其中VPI、VCI的变化情况是(25)。如果在交换过程中出现拥塞,该信息被记录在信
S-HTTP协议对C/S结构是(30)的,与HTTP协议的区别是使用了协议指示器。
ISO9000系列标准和软件成熟度模型(CMM)都着眼于质量和过程管理。ISO9000系列标准强调质量管理必须坚持进行(9)。
以下关于光纤通信的叙述中,正确的是______。
ThedefactostandardApplicationProgramInterface(API)forTCP/IPapplicationsisthet•sockets”interface.AlthoughthisAPlwa
要将一个IP地址为206.17.45.0的网络分解为多个子网,每个子网要25个主机ID并要求尽可能多的子网。指定子网掩码为__________。
SSL是一个介于(1)与TCP之间的一个可选层,当发送访问请求时,在SSL层,借助下层协议的安全信道(2),并用此来(3)。在TCP层,与服务器端口建立连接,传递SSL处理后的数据。接收端的操作与此发送端过程相反。SSL协议分为(4)和记录协议两部分。其中
关于明文和密文,叙述不正确的是(1)。对明文字母重新排列,并不隐藏它们的加密方法属于(2);在20世纪70年代之前使用的加密机制为(3):DES算法即采用了这种加密技术;公钥加密体制中,没有公开的是(4),下面描述正确的是(5)。(2)
客户/服务器模式产生于20世纪(27)上年代,它是基于(28)的要求而发展起来的。客户/服务器模式的第一个软件产品是(29)系统,客户/服务器模式通常在(30)环境下运行,客户端的软件具有(31)。
随机试题
高血压脑出血最常发生于()
女,32岁。颜料厂工人,工龄5年,近半年来头昏、乏力,阵发性脐周隐痛。其原因最有可能的是
肥皂刷手法中需将上肢浸泡在70%乙醇内,是手至肘上()
下列各项中,在资产负债表日后至财务报告批准报出日之间发生的属于资产负债表日后非调整事项的有()。
天主教中的最高级主教称“枢机主教”,俗称“()”。
在互联网出版中,信息网络安全保护体系的构建主要涉及技术控制和()方面的内容。
近些年来,价值观问题受到社会各界的高度重视。但是,作为价值观核心概念的“价值”及相关概念,在国内理论界一直存在着许多似是而非的看法,影响了我们对价值观问题的理解,因而有必要厘清一些基本概念。现代价值观的“价值”概念,直接来自于经济学的使用价值,但
在Excel中,假设单元格A1、A2、A3和A4的值分别为23、45、36、18,单元格B1、B2、B3、B4的值分别为29、38、25、21。在单元格C1中输入“=SUM(MAX(A1:A4),MIN(B1:B4))”(输入内容不含引号)并按Enter后
通过宏查找下一条记录的宏操作是【】。
PassageOneITEMONEFORSALE:OceanKayakFrenzy,BrightYellow,$300;noaccessories.Theirkayakhasbeenstoredintheg
最新回复
(
0
)