文法G=(VT,VN,P,S)的类型由G中的(21)决定。若GO=({a,b},{S,X, Y},P,S),P中的产生式及其序号如下:
1:S→XaaY
2:X→YY|b
3:Y→XbX|a
则GO为(22)型文法,对应于(23),由GO推导出句子aaaa和baabbb时,所用产生式序号组成的序列分别为(24)和(25)。
A.VT
B.VN
C.P
D.S
第1题:
己知文法G2=(VT={a,',',(,)},VN={S,L},S,P),其中P为, S→(L)|a L→L,S|S 右句型(L,(L,S))的句柄是(28)。
A.(L,(L,S))
B.(L,S)
C.L,S
D.S
第2题:
已知文法G2=(VT={a,',',(,)},VN{S,L},S,P),其中P为, S→(L)|a L→L,S|S (a,(a,a))是L(G2[S])的句子,这个句子的最左推导是(28)
A.
B.
C.
D.
第3题:
设语言L={w|w∈{a,b}+且w中a和b的个数相等},产生语言L的上下文无关文法是(28)。
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
第4题:
已知文法G2=(VT={a,',',(,)},VN={S,L),S,P),其中P为 S→(L)|a L→-L,s|s 与G2等价的不含左递归规则的文法是(29)。
A.G21=(VT={a,',',(,)},VN={S,L},S,P),其中P为 S→(L)|a L→S,S|S
B.G22=(VT<a,',',(,)},VN={S,L,L'},S,P),其中P为 S→(L)|a L→SL' L'→SL'|ε
C.G23=(VT{a,',',(,)},VN={S,L,L'},S,P),其中P为 S→(L)|a L→SL' U→,SL'|ε
D.G24=(VT=(a,',',(,)},VN=<S,L,L'},S,P),其中P为 S→(L)|a L→SL' L→SL'|S
第5题:
已知文法G1=(VT={a,b,d},VN={S,A,B},S,P),其中P为: S→dAB A→aA|a B→bB|ε 该文法属于(28)文法。
A.0型
B.上下文有关
C.上下文无关
D.正规
第6题:
文法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
第7题:
已知文法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.
第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,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