已知文法G1=(VT={a,b,d},VN={S,A,B},S,P),其中P为, S→dAB A→aA|a B→bB|ε 该文法生成的语言是(28)。
A.{dambn|m≥0,n≥O}
B.{dambn|m≥1,n≥0}
C.{dambn|m≥0,n≥1}
D.{dambn|m≥1,n≥1}
第1题:
ASAT
BB
CfSg
De
第2题:
线性链表中结点的结构为(data,next)。已知指针p所指结点不是尾结点,若在*p之后插入结点*s,则应执行下列()操作。
A.s->next=p;p->next=s;
B.s->next=p->next;p->next=s;
C.s->next=p->next;p=s;
D.p->next=s;s->next=p;
第3题:
●文法G=(VT,VN,P,S)的类型由G中的 (32) 决定。若G0=({a,b},{S,X,Y},P,S),P中的产生式及其序号如下:
1:S→XaaY
2:X→YYlb
3:Y→XbXla
则G0为 (33) 型文法,对应于 (34) ,由G0推导出句子aaaaa和baabbb时,所用产生式序号组成的序列分别为 (35) 和 (36) 。
(32) A.VT
B.VN
C.P
D.S
(33) A.0
B.1
C.2
D.3
(34) A.图灵机
B.下推自动机
C.有限状态自动机
D.其他自动机
(35),(36) A.13133
B.12312
C.12322
D.12333
【解析】形式语言的文法是一个4元组G=(VT,VN,P,S),其中VT是非空有限集,称为终端符集,VN也是非空有限集,称为变量集;P为产生式集;S为起始符,S∈VN。形式语言的文法按P的特性可分成正则文法、上下文无关文法、上下文有关文法和图灵文法4种类型,又分别称为3型、2型、1型和0型文法。所对应的可实现的自动机分别为有限状态自动机、下推自动机、线性有界自动机和图灵机。本题中给出的文法、生产式左部均是单个变量,因此是上下文无文法。由此文法导出句子aaaaa的产生式号的序列及推导过程如下:
S→XaaY1→YYaaY2→aYaaY3→aaaaY3→aaaaa 3句子baabbb的推导过程为:
S→XaaY1→baaY2→baaXbx3→baabbx 2→baabbb2因而产生式号的序列是12333和12322
第4题:
A.以终结符 a1,a2,…,an 为运算对象的布尔表达式串
B.以∨,∧,~为运算符,以[、]为分隔符的布尔表达式串
C.以终结符 a1,a2,…,an 为运算对象,以∨,∧,~为运算符,以[、]为分隔符的布尔表达式串
D.以[、]为分隔符的布尔表达式串
第5题:
文法G=(VT,VN,P,S)的类型由C中的(32)决定。若GO=({a,b},{S,X,Y},P,S),P中的产生式及其序号如下:
1:S→XaaY
2:X→Dqb
3:Y→XbXla
则GO为(33)型文法,对应于(34),由GO推导出句子aaaaa和baabbb时,所用产生式序号组成的序列分别为(35)和(36)。
A.VT
B.VN
C.P
D.S
第6题:
已知文法G2=(VT={a,',',(,)},VN={S,L),S,P),其中P为,
S→(L)|a
L→L,S|S
(a,a)是L(G2)的句子,这个句子的分析树是(28)。
A.
B.
C.
D.
第7题:
考虑下述文法,S为开始符号 G1[S]:S→A A→aAb | ab G2[S] S→AA→aA |a| 下列结论中为真的是(28)。
A.G1是LR(0)文法,G2不是LR(1)文法
B.G2是LR(0)文法,G1不是LR(1)文法
C.G2是LR(1)文法,G1不是LR(1)文法
D.G1和G2都是LR(1)文法
第8题:
● 对给定文法G=(VN,VT, P,S),VT={a,Λ,(,)},VN={S,T},S是开始符号,
P:
S→a|Λ|(T)
T→T,S|S
则(1)不是它的句子。该文法是(2)型文法。
(1)A. (a,(a,a)) B. (((a,a), Λ,(a)),a) C. ((a,a), Λ) D. ((a,a),(T))
(2)A.0型文法 B.1型文法 C.2型文法 D.正规文法
第9题:
考查下列文法:
G(VT,VN,E,P)
其中:Vsub>T={+,*,(,),i);VN={E,T,F};E是开始符号;P为:
E→E+T|T
T→T*F|F
F→(E)|i
F*F+T是该文法的一个句型,其中(1)是句柄,(2)是素短语,(3)是该句型的直接推导,(4)是该句型的最左推导,(5)是该文法的一个句子。
A.F
B.F*F
C.F+T
D.F*F+T
第10题:
假设某程序语言的文法如下:
S→a|b|(T)
T→TdS|S
其中:VT={a,b,d,(,)},VN{S,T},S是开始符号。
考查该文法,称句型(Sd(T)db)是S的一个(33),其中,(34)是句柄:(35)是素短语;(36)是该句型的直接短语;(37)是短语。
A.最左推导
B.最右推导
C.规范推导
D.推导