2 0 1 X ε 1 ε Y 0
第三步：确定化，得到DFA。确定化结果如表14.1所列；给状态编号，得到表14.2所示的状态转换矩阵： 状态 0 1 状态 0 1 {X，1，Y} {1，Y} {2} 0 1 2 {1，Y} {1，Y} {2} 1 1 2 {2} {1，Y} ? 2 1 表14.1 状态转换矩阵 表14.2 新的状态转换矩阵 根据状态转换矩阵得到DFA如下图所示：
0 1 2 0 1 0 1 0
第四步：对该DFA进行最小化。其分析过程如下： {0，1}，{2}
{0，1}0={1}，{0，1}1={2} {0，1}，{2}
最小化后的DFA如图所示，该DFA即为所求。
0 1 0 0 1
15、 给定右线性文法G： S→0S∣1S∣1A∣0B A→1C∣1 B→0C∣0
C→0C∣1C∣0∣1
求出一个与G等价的左线性文法。
分析：根据右线性文法求左线性文法没有直接的方法，但可以通过状态转换图去转换。可以先求出文法G的状态转换图，再根据状态转换图写出相应的左线性文法。文法G对应的状态转换图如下所示：
0，1 S 1 A 0 B 0 1 0，1 C 1 0，1 Z 0
对状态转换图进行确定化，得到状态转换矩阵： 状态 0 1 {S} {S，B} {S，A} {S，B} {S，B，C，Z} {S，A} {S，A} {S，B} {S，A，C，Z} {S，B，C，Z} {S，B，C，Z} {S，A，C，Z} {S，A，C，Z} {S，B，C，Z} {S，A，C，Z} 给状态编号，得到新的状态转换矩阵： 状态 0 1 0 1 2 1 3 2 2 1 4 3 3 4 4 3 4 根据状态转换矩阵获得DFA如下： 0 0 1 2 0 1 0 1 1 0 1 4 1 3 0
还可以对上图的DFA进行化简，状态3和4可以合并，化简后的DFA如下图所示：
0，1 0 0 S A 1 0 B T 1 1
不难看出，该DFA接受的语言是{0，1}上包含00或11的字符串。根据化简后的DFA，我们可以写出相应的左线性文法G’： T→A0∣B1∣T0∣T1 A→B0∣0 B→A1∣1
16、 *非形式的说明
17、 *下面的字集是否为正规集？或写出其正规式，或给出否证。
（1） L1={anbn∣n≥0}； （2） L2={x}； （3） L3={}。
18、 假定L和M都是正规集：
（1） 证明L∪M、L∩M和～M（补集）也是正规的； （2） L′是L中每个字的逆转，证明L也是正规的。
19、 写出描述ANSI C的单词符号的LEX程序。
20、 假定有正规定义式 A0→a∣b A1→A0 A0
??
An→An-1 An-1
考虑词形An
（1） 把An中所有简名都换掉，最终所得的正规式的长度是多少？ （2） 字集An的元素是什么？把它们非形式的表示成n的函数； （3） 证明识别An的DFA只需用2n+1个状态就足够了。
21、 把LEX的“动作”成分加以充实使得可用它来编写语法制导编辑器。
第四章 语法分析——自上而下分析
1、考虑下面的文法G1： S→a∣∧∣(T) T→T，S∣S （1）消去G1的左递归。然后对每个非终结符，写出不带回溯的递归子程序。 （2）经改写后的文法是否是LL(1)的？给出它的预测分析表。 解：
（1）按照T、S的顺序消除左递归，得到文法： G’(S)
S→a∣∧∣(T)
T→ST’
T’→，ST’ ∣ε
对于非终结符S,T, T’的递归子程序如下： Procedure S; Begin If sym = ‘a’ or sym = ‘^’ Then advance Else if sym = ‘(‘ Then begin Advance ; T; If sym = ’)’ Then advance Else error End Else error Ends;
Procedure T; Begin S; T’; Ends;
Procedure T’ Begin
If sym = ‘,’ Then begin Advance ; S; T’ Ends
ends;
? （2）计算每个非终结符的FIRST集合和FOLLOW集合： FIRST（S）={a，∧，( } FIRST（T）={a，∧，( } FIRST（T’）={，，ε} FOLLOW（S）={ )，’，’，#} FOLLOW（T）={ ) } FOLLOW（T’）={ ) }
从而可见改造后的文法符合LL(1)文法的充分必要条件，所以是LL(1)的。 该文法的预测分析表 a ^ ( ) , # S S->a S->^ S->(T) T T->S T’ T->S T’ T->S T’ T’->ξ T’ T->,S T’ 2、对下面的文法G： E→TE’ E’→+E∣ε T→FT’ T’→T∣ε F→PF’ F’→*F’∣ε
P→(E)∣a∣b∣∧
（1） 计算这个文法的每个非终结符的FIRST和FOLLOW。 （2） 证明这个文法是LL(1)的。 （3） 构造它的预测分析表。
（4） 构造它的递归下降分析程序。
分析：对于这类题目，我们首先应当检查文法是否符合LL(1)文法的条件，根据需要，先通过消除左递归、提取右公因子的方法，把文法改造成符合LL(1)文法的条件，在此基础上，我们才能构造出不带回溯的递归下降识别程序。注意，本题在构造子程序时，对于每个产生式候选，在调用第一个非终结符对应的子程序之前，检查了首符集。 解：
（1） 计算每个非终结符的FIRST集合和FOLLOW集合如下： FIRST（E）={(，a，b，∧} FIRST（E’）={+，ε} FIRST（T）={(，a，b，∧} FIRST（T’）={(，a，b，∧，ε} FIRST（F）={(，a，b，∧} FIRST（F’）={*，ε} FIRST（P）={(，a，b，∧} FOLLOW（E）={#，)} FOLLOW（E’）={#，)}