精品
8、对任何正规表达式e，都存在一个DFA M，满足L(G)=L(e)。 （ ） 五、基本题
1、设M＝（{x,y}, {a,b}, f,x,{y}）为一非确定的有限自动机，其中f定义如下：
f（x,a）＝{x,y} f（x,b）＝{y} f（y,a）＝φ f（y,b）＝{x,y}
试构造相应的确定有限自动机M′。 2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M；
单选解答 1、b 2、c 3、c 4、d 5、b 多选解答 1、a、c、e 2、a、b、d
填空解答 1、NFA 2、正规集 3、DFA（NFA）所识别 判断解答 1 、2、3、错 4、5、6、7、8、正确
基本1解答：对照自动机的定义M=(S,Σ,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图3-6-2所示。 a a b X b Y b 用子集法构造状态转换矩阵表3-6-3所示。 I {x} {y} {x,y} Ia {x,y} — {x,y} 图3-6-2 NFA M Ib {y} {x,y} {x,y} 将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。 表3-6-4 状态转换矩阵 0 1 2 a 2 — 2 b 1 2 2 即得到M′=（{0,1,2}, {a,b}, f,0, {1,2}），其状态转换图如图3-6-5所示。
a 0 2 a,b 1 b b 感谢下载载
精品
将图3-6-5的DFA M′最小化。首先，将M′的状态分成终态组{1，2}与非终态组{0}；其次，考察{1,2}。由于{1,2}a={1,2}b={2}?{1,2}，所以不再将其划分了，也即整个划分只有两组{0}，{1,2}：令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图3-6-6所示化简DFA M′。
a a,b
1 0 b
图3-6-6 化简后的DFA M′
2解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，
b*(d|ad)(b|ab)(b|ab)* X Y 如图3-6-7所示。
X ε X ε X b* b 4 ε b 4 ε 1 a 1 ad d 2 a 6 d 1 (d|ad) d 2 ab b 2 (b|ab) b *3 (b|ab) Y b|ab 3 ε 5 ε b 3 ε 5 a 7 b 8 ε Y b Y 图3-6-7 的NFA M
感谢下载载
精品
第四章
1、 构造下面文法的LL（1）分析表。
D→ TL T→ int | real L→ id R R→ , id R | ε
2、 下面文法G[S]是否为LL（1）文法？说明理由。
S → A B | P Q x A → x y B → b c P → d P | ε 3、 设有以下文法：
G[S]：S→aAbDe|d
A→BSD|e B→SAc| cD| ε D→Se| ε
Q → a Q | ε
（1）求出该文法的每一个非终结符U的FOLLOW集。 （2）该文法是LL（1）文法吗？ （3）构造C[S]的LL（1）分析表。 4、 将文法G[V]改造成为LL(1)的。
G[V]：V→N|N[E]
感谢下载载
精品
E→V|V+E N→i 5、已知文法：
G[A]： A→aAa|ε
（1）该文法是LL（1）文法吗？为什么？
（2）若采用LL（1）方法进行语法分析，如何得到该文法的LL（1）分析表？ （3）若输入符号串“aaaa”，请给出语法分析过程。 1解答： LL（1）分析表见表4-3-1
分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。 FIRST（D）=FIRST（T）={int, real}
FOLLOW（D）=FOLLOW（L）={#}
FIRST（L）={id} FOLLOW（T）={id} FIRST（R）={，, ε} FOLLOW（R）={#}
有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部α的FIRST（α）就不是件难事了。
填表时唯一要小心的时，ε是产生式R→ε右部的一个开始符号，而#在FOLLOW（R）中，所以R→ε填在输入符号#的栏目中。
表4-3-1 LL（1）分析表
非终结符 D T L int D→TL T→int 输入符号 real D→TL T→real id L→id R ， # 感谢下载载
精品
R
R→,id R R→ ε 2解答： 该文法不是LL（1）文法，见下面分析中的说明。 分析 只有三个非终结符有两个选择。
1、P的两个右部d P 和ε 的开始符号肯定不相交。
2、Q的两个右部a Q 和 ε 的开始符号肯定不相交。
3、对S来说，由于x ∈ FIRST(A B)，同时也有x ∈ FIRST(P Q x)（因为P和Q都可能为空）。所以该文法不是LL（1）文法。
3解答： （1）求文法的每一个非终结符U的FOLLOW集的过程如下：
因为：
① S是识别符号，且有A→BSD、B→SAc、D→Se，所以FOLLOW（S）应包含
FIRST(D)∪FIRST(Ac) ∪FIRST(e) ∪{#} ={a,d}∪{a,d,c,e}∪{e}∪{#} ={a,c,d,e#}
② 又因为A→BSD和D→ε，所以FOLLOW中还包含FOLLOW(A)。 因为S→aAbDe和B→SAc,所以
FOLLOW（A）=FIRST（bDe）∪FIRST（c）={b,c}
综合①、②得FOLLOW（S）={a,d,c,e,#}∪{a,b,c,d,e,#} 因为A→BSD，所以 FOLLOW（B）=FIRST（SD）={a,d} 因为S→aAbDe | d、A→BSD| e和B→SAc | cD，所以
FOLLOW（D）=FIRST（e）∪FOLLOW（A）∪FOLLOW（B）
={e}∪{b,c}∪{a,d}={a,b,c,d,e} （2）G[S]不是LL（1）文法。
感谢下载载