首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
admin
2013-05-11
32
问题
设语言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
软件设计师上午基础知识考试
软考中级
相关试题推荐
Inter公司用于网络处理的IXP系统微处理器支持DDR内存接口。在200MHz外频条件下,DDR内存带宽可达(3)。
下述任务中,(2)不属于软件工程需求分析阶段。
单个磁头在向盘片的磁性涂层上写入数据时,是以(3)方式写入的。
RS-232C是(34)之间的接口标准,其规定的电平表示方式为(35)。当使用RS232C连接相关设备时,电缆的长度不应超过(36)m。当用RS232C直接连接两台计算机时,采用零调制解调器方式,其连接方式为(37)。当计算机需要通过相连的MO-DEM
在广播介质网络OSPF配置过程中,在路由器RouterA配置子模式下键入showipospfneihbor命令获得如图8-6所示的系统输出信息,具有最高路由器ID的是(52)。
入侵检测系统(IDS)是一类专门面向网络入侵检测的网络安全监测系统,其基本功能包括:检测出(1);发现攻击活动的范围和后果;诊断并发现攻击者的入侵方式和入侵地点,并给出解决建议;收集并记录(2)。IDS系统还可以(3)。IDS系统的服务功能
10Base-T以太网使用曼彻斯特编码,其编码效率为(1)%,在快速以太网中使用4B/5B编码,其编码效率为(2)%。(2011年上半年试题)(1)
内存单元按字节编址,地址0000A000H~0000BFFFH共有()个存储单元。
在多个用户共享数据库时,对同一资料的1._____操作可能破坏数据库的2.______。因此数据管理机制要解决丢失更新、不一致以及3.______等问题。解决的方法主要有加锁技术和时标技术。3.____A.“脏数据”B.安全
随机试题
下列药物须舌下给药的是
哺乳期妇女用药,下列哪项是错误的()
下列流水参数中,不属于空间参数的是()。
一般意义上的优先股具有的特点之一是在发行时事先确定()。
合同约定由债务人甲向第三人乙履行交货义务,甲在所交货物的质量不符合合同约定时,应当向乙承担违约责任。()
15周岁的人违反治安管理的,不予处罚,但是应当责令其监护人严加管教。()
党是领导我国现代化事业的核心力量,只有党才能够动员和领导政、军、工、农、商、学、青、妇等社会各界,也只有党才能对人民群众有最大的号召力。()
RarelyhavetheChristmasresultsforBritain’ssupermarketsbeenawaitedwithsuchanxiety.Mostofthem,especiallythemarke
以下程序运行后的输出结果是【】。#include<stdio,h>main()charc1,c2;for(el=’0’,c2=’9’;e1<c2;c1++,c2--)printf("%c%
Someyoungchildrenspendagreatamountoftheirtimepracticingsports.Discusstheadvantagesanddisadvantagesofthis.Use
最新回复
(
0
)