定义如下δ（q0，0）q1δ（q0，1）q0δ（q1，0）q2δ（q1，1）q0δ（q2，0）q2δ（q2，1）q0
b正则表达式1010101DFAM0，1，q0，q1，q2，q3，q0，q3，δ其中δ定义如下δ（q0，0）q1δ（q0，1）q0δ（q1，0）q2δ（q1，1）q1δ（q2，0）q3δ（q2，1）q2δ（q3，1）q3
37构造等价于下列正规表达式的有限自动机。110（011）0120111
答案1DFAM0，1，q0，q1，q2，q3，q0，q3，δ其中δ定义如下
精品文档
f精品文档
2δ（q0，0）q1δ（q0，1）q23δ（q1，0）q1δ（q1，1）q34δ（q2，0）q3δ（q2，1）q1
5
62DFAM0，1，q0，q0，q0，δ7其中δ定义如下8δ（q0，0）q0δ（q0，1）q0
9
38给定右线性文法G：S0S1S1A0BA1C1B0C0C0C1C01试求一个于G等价的左线性文法G39试对于下列正规表达式使用证明定理3。5的构造算法构造非确定的有限自动机。请给出每个自动机在处理输入符号串ababbab的过程中的动作序列。1ab2ab3εab
精品文档
f精品文档
310转换练习39中的每个NFA为DFA。并给出每个DFA在处理输入符号串ababbab的过程中的动作序列。
311试把练习310中得到的DFA的状态给以最小化。
答案123的DFAM相同，化简结果为：
4
312我们可以证明两个正规表达式是等价的，如果它们的最小状态DFA是相同的（除了状态的名字以外）。利用这一结论，请说明下列正规表达式都是等价的。1ab2ab3εab
答案根据311的结果知这几个正规表达式是等价的。
313对于下列正规表达式构造最小状态的DFA。1abaab2abaabab5．对如下文法：
GS：SabSaaBadBbbBb
分别给出句子abaabbb和ad的句柄句子ad的语法分析树为：
精品文档
f精品文档a
Sd
句子abaabbb的语法分析树为
S
a
b
S
a
B
a
b
b
B
b
所以句子abaabbb的句柄是b；句子ad的句柄是ad
二、（10分）说明如下文法是否是LL（1）文法，若不是，将其转换为LL（1）文法。最后给出该文法的
LL（1）分析表。
GA：
ABeBBba
文法中有左递归，不是LL1文法。
转换为G′：ABe
BaB′
B′bB′λ
PredictABea
PredictBaB′a
PredictB′bB′b
PredictB′λe
LL1分析表
a
b
e
A
Be
B
aB′
B′
bB′
λ
精品文档
f精品文档4给出识别正则表达式（abc）d的NFA。
5．已知文法GS：S→S；G│G
G→GT│H
H→a│S
T→TS│S
找出句型：aTS；H；S的短语、简单短语和句柄。
短语aTSaTSHaTSHS
简单r