全球旧事资料 分类
箧怼类蒋

63.如图所示自动机M,请问下列哪个字符串不是M所能识别的D。
Abbaa
Babba
Cabab
Daabb
f64.有限状态自动机能识别CA上下文无关语言B上下文有关语言
C正规语言
D0型文法定义的语言
65.已知文法G是无二义的,则对G的任意句型αAA最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能相同C最左推导和最右推导必定相同D可能存在两个不同的最左推导,但他们对应的语法树相同
66.B不是DFA的成分A有穷字母表B多个初始状态的集合
C多个终态的集合
D转换函数
67.与逆波兰式后缀表达式abcd对应的中缀表达式是B
AabcdBabcdCabcdDabcd
68.后缀式abcd可用表达式B来表示。A.abcdB.abcdC.abcdD.abcd厦礴恳蹒骈继骚。
69.表达式ABCCD的后缀式为B。A.ABCCDB.ABCCDC.ABCCDD.以上都不对
70.D不是NFA的成分。
A有穷字母表
B初始状态集合
C终止状态集合
D有限状态集合
二、问答题
1.将文法GS改写为等价的G′S,使G′S不含左递归和左公共因子。GS:S→bSAebA
A→Abd答:
文法GS改写为等价的不含左递归和左公共因子的GS为:
S→bB
B→SAeA
fA→dA
A→bAε2.将文法GS改写为等价的GS,使GS不含左递归和左公共因子。
GS:S→SAeAe
答:
A→dAbAdAd
文法GS改写为等价的不含左递归和左公共因子的GS为:
S→AeS
S→AeSε
A→dA
A→ABε
B→bAε3.将文法GS改写为等价的GS,使GS不含左递归和左公共因子。
GS:S→A
A→BAS
答:
B→aBa
文法GS改写为等价的不含左递归和左公共因子的GS为:
S→A
A→BA′
A′→SA′ε
B→aB′
B′→Bε4.判断下面文法是否为LL1文法,若是请构造相应的LL1分析表。
S→aH
H→aMdd
M→Abε
A→aMe答:
首先计算文法的FIRST集和FOLLOW集如下表。
f非终结符SHMA
文法的FIRST集和FOLLOW集FIRST集aa,d
a,e,εa,e
FOLLOW集
d,bb
由于predict(H→aMd)∩predict(H→d)a∩d
predict(M→Ab)∩predict(M→ε)a,e∩d,b
predict(A→aM)∩predict(A→e)a∩e
所以该文法是LL1文法,LL1分析表如下表。
a
d
b
e

S
→aH
H
→aMd
→d
M
→Ab
→ε
→ε
→Ab
A
→aM
→e
5.判断下面文法是否为LL1文法,若是,请构造相应的LL1分析表。
S→aDD→STeε
T→bHH
H→dε
答:
首先计算文法的FIRST集和FOLLOW集如下表。
非终结符
FIRSTr
好听全球资料 返回顶部