箧怼类蒋
。
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