首页/ 题库 / [单选题]设语言L={w|w∈{a,b}+且w中a的答案

设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。

单选题
2022-02-27 19:35
A、Ga=(VT={a,b},VN={S,A,B},S,P),其中P为, S→a|aA|bSS A→aB|bS B→b|bA|aBB
B、Gb=(VT={a,b},VN={S,A,B},S,P),其中P为, S→b|bB|aSS B→aS|bA A→a|aB|bAA
C、Gc=(VT={a,b},VN{S,A,B},S,P),其中P为, S→aB|bA A→a|aS|bAA B→b|bS|aBB
D、Gd=(VT={a,b},VN={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(Ga)={w|w∈{a,b}+且w中a比b的个数多一个}L(Gb)={w|w∈{a,b}+且w中b比a的个数多一个}L(Gc)={w|w∈{a,b}+且w中a和b的个数相等}L(Gd)={w|w∈{a,b}+且w中a和b的个数相等}

标签:
感兴趣题目
根据乔姆斯基20世纪50年代建立的形式语言的理论体系,语言的文法被分为四种类型,即:O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(67)。从文法描述语言的能力来说,(68)最强,(69)最弱,由四类文法的定义可知:(70)必是2型文法。(40)
已知文法G2=(VT={a,b},VN={S,A},S,P),其中P为, S→Sb|Ab A→aSb|ε 该文法生成的语言是(28)。
在形式语言中,若文法G的产生式集P为:(1)Z→Bc(2)Z→Zc(3)B→Ab(4)B→Bb(5)A→Aa(6)A→a则文法G是(27)文法,识别G的自动机为(28)。对于G来说,(29)为文法G可接受的字符串,(30)为文法G不可接受的字符串。供选择的答案:
已知点A(20,8,8),与点A对称于W面的点B的坐标值是()
A地坐标为(20°N,113°E),B地坐标为(21°S,78°W),则A在B的()。
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
从A,B两地土层中个取粘性土进行试验,恰好其液塑限相同,液限wl=45%,塑限wp=30%,但A地的天然含水率为45%,而B地的天然含水率为25%。试求A,B两地的地基土的液性指数,并通过判断土的状态,确定哪个地基土比较好。
已知文法G:S→WZ W→X|Y X→a|aX Y→b|bY Z→c|cZ,G定义的语言的相应正规式为( )。
基础底面抵抗矩W=bl2/6,其中b、l分别表示基础底板()、()的尺寸。
尺寸字U、V、W表示增量()坐标,A、B、C表示()坐标。
有以下程序: int f1(doubleA){return a*a;} int f2(int x,int y) {double a,b; a=f1(x); b=f1(y); return a+b; } main() {double w; w=f2(2.1,4.0); } 程序执行后,变量w的值是( )。
企业的短期劳动力需求曲线为w=10-L,这里w为真实工资,L为劳动需求数量。那么,当市场上的均衡工资率为w*=5时,企业在最佳雇佣量下支付的工资总额是()
相关题目
A市B县的W房地产开发公司,取得了B县城中某住宅土地的使用权,按照规定,建设用地使用权出让合同由()与W房地产开发公司签订。
已知各变量的类型说明如下: Int i=8,k,a,b; Unsigned long w=5; Double x=1.42,y=5.2; 则以下符合C语言语法的表达式是( )
设int k,a,b;unsigned long w=5;double x=1.42; 则不符合类型要求的表达式是( )
普通混凝土的强度公式f28=αafc(C/W-αb)中,在()条件下, αa、αb为常数。
设: float w; int a, b;则合法的switch语句是(   )。
某岩层的产状为北偏西320°,倾向南西230°,倾角为25°,一般可写为N320°W,S230°W,∠25°。 A正确 B错误
已知氨水的密度比纯水小,若以W1和W2分别表示amol/L和bmol/L氨水质量分数且2a=b,则下列推断正确的是()。
设有文法G[W]:W→A0A→A0|W1|0,改写文法消除左递归
B点和A点的()面投影重合,称为W面的重影点。
基础底面抵抗矩W=bl2/6,其中b、l分别表示基础底板()、()的尺寸。
若有以下程序段,w和k都是整型变量。w=k;LB:if(w==0)goto LE; w--; printf("*"); goto LB;LE: M则不能与上面程序段等价的循环语句是A.for(w=k;w!=0;w--)printf("*");B.w=k;<CR>while(w--!=0)printf("*");w++;C.w=k;<CR>do { w--;printf("*");}while(w!=0);D.for(w=k;w;--w)printf("*");
执行下列程序后,w的值为( )。 intw=A,x=14,y=15; w=((x‖y)&&(w<a));
芭蕾舞bā lěi wǔ
设A、B、C均为n,阶矩阵,则 (1)若A≠B,则|A|≠|B| (2)若AB=AC,且A≠0,则B=C (3)若A2=E,且A≠E,则A=-E (4)若A可逆,且A-1B=CA-1,B=C 则上述命题中,正确命题的个数是__。
设A、B、C均为n阶矩阵。 ①若A≠B,则|A|≠|B| ②若AB=AC,且A≠0,则B=C ③若A2=E,且A≠E,则A=-E ④若A可逆,且A-1B=CA-1,则B=C 则上述命题中,正确的命题个数为()。
已知文法G[S]为:S→dAB;A→aA|a;B→Bb|ε;G[S]产生的语言是什么?
● 程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法G=(N,T,P,S),其中 N是非终结符号的集合,T 是终结符号的集合,P是产生式集合,S 是开始符号。令集合 V= N∪T,那么 G 所描述的语言是 (50) 的集合。(50)
程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法 G=(N,T,P,S),其中N是非终结符号的集合,T是终结符号的集合,P是产生式集合,S是开始符号。令集合V=N∪T,那么G所描述的语言是(50)的集合。
程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法G=(N,T,P,S),其中N是非终结符号的集合,T是终结符号的集合,P是产生式集合,S是开始符号。令集合V=N∪T,那么G所描述的语言是(29)的集合。
●根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,语言的文法被分为4种类型,即0型(短语文法),1型(上下有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与 (28) 等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价 (29) 。从文法描述语言的能力来说, (30) 最强, (31) 最弱,由4类文法的定义可知: (32) 必是2型文法。线性有限自动机非确定的下推自动机图灵机有限自动机(29)
广告位招租WX:84302438

免费的网站请分享给朋友吧