1. 将图1所示的有穷自动机转换成与其等价的正规文法，其中4、5为终止状态。 解答：本题考查有穷自动机到正规文法的转换方法。
这类题只需要书中所介绍的方法进行即可得到正规文法，本题有穷自动机对应的正规文法G[S]为：
A→aB|bB|cC
B→aB|bD|aE|cC|b|a C→bB|cC|cE|c D→bD|b E→aE|a
b a 2 b
4
start
b a 1
b c 3 c c 5 a
图1有穷自动机的状态转换图
2.给定如图2所示的有穷自动机，试用正规表达式给出它能接受的语言集合。
b b 0 a 1 a b a a 2 b 3
图2有穷自动机
解：本题考查正规表达式与有穷自动机的等价性。
对于一个在输入字母表∑上的FAM，一定可以在字母表∑上构造一个正规表达式e，使得L(e)=L(M) .
根据状态转换图，从开始状态出发，可以有任意个（包括0个）b作为句子的开始部分；从0状态出发，每输入一个a，不许输入两个b才能到达终止状态后，还可以通过输入a回到状态1，或输入b回到状态0，然后进入递归过程，再输入相同的符号串，所以，该有穷自动机描述的语言为：
(b*(aa*b)*b)*
3. 构造下述正规表达式的DFA。 Xy*|yx*y|xyx
解： 本题考查由正规表达式构造有穷自动机的方法，
本题可按照由正规表达式构造等价的NFA，NFA确定化，DFA最小化3步进行求解。 （1） 根据题中所给的正规表达式得到相应的DFA如图3所示。
y A x y ε C ε B ε x D ε y S E Z x F y G x 图3正规表达式Xy*|yx*y|xyx的DFA。
（2） 依据该NFA采用子集法构造确定DFA其过程如表1（已换名）所示。 表1 将NFA确定化为DFA的过程 I Ix Iy [S] [A, B, F, Z] [C, D, E] [B, G, Z] [D, E] [Z] 0 1 2 3 4 5 [A, B, F, Z] [D, E] [Z] [D, E] 1 4 5 4 [C, D, E] [B, G, Z] [Z] [B, Z] [Z] 2 3 5 6 5
[B, Z] 6 [B, Z] 6 以所有包含NFA的终止状态Z的DFA状态作为终止状态，得到DFA相应的状态转换图如 图4所示
x 1 y x 3 y x 4 y 6 0 y x 2 y y 5 5 图4 DFA的状态转换图
（3） 对DFA进行最小化，过程如下：
已知K={0,1,2,3,4,5,6}。首先将K分成两个子集 K1={0,2,3} （非终态集） K2={1,3,4,6} （终态集） 在状态集合K1={0,2,3}中，因为 {0}x={1}?K2 {2,4}x={4}?K1
所以状态0与状态2，4不等价，故K1可分割为 K11={0} K12={2,4} 在状态集合K12={2，4}中，因为有 {2，4}x={4} {2,4}y={5}?K2 所以，状态2和状态4等价。
在状态集合K2={1,3,4,6}中，状态5无输入，状态3有x、y输入，状态1与状态6只有y输入，所以可将K2分割为
K21={1,6} K22={3} K23={5}
在状态集合K21={1，6}中，状态1输入y到达状态3，状态6输入y到达状态6，所以状态1与6也不等价。进一步将K21分割为 K211={1} K212={6}
于是，将原状态集合划分为：{0}、{2，4}、{1}、{3}、{5}、{6}。 选{2，4}中的2作为代表，原来由状态4导入（出）其余状态的弧改为有状态2导入（出）；然后消去状态4。最后得到最小化后的状态转化图如图5所示。
x 1 y 3 y 6 0 x y x y 2 y 5 5 图5正规表达式Xy*|yx*y|xyx的最小化DFA
4. 构造正规表达式（011）*00相应的DFA。
解：本题考查由正规表达式构造确定的有穷自动机的方法。 （1） 构造正规表达式（011）*00的DFA。
按照图3.2所示的转换规则构造正规表达式（011）*00对应的NFA如图6所示。
0 ε S A 1 ε B 0 C 0 Z
图6正规表达式（011）*00的DFA
（2） 由正规表达式（011）*00的NFA构造确定的有穷自动机DFA。
以NFA的开始状态S的ε闭包ε-CLOSURE（{S}）作为DFA的开始状态，采用子集法将图3.43中所式的NFA确定化，其过程如表2所示。
表2 将NFA确定化为DFA的过程 I Ix Iy [S，A, B] 0 [A, B, C] 1 [A, B] 2 [A, B, C] [A, B] 1 2 [A, B, C, Z] [A, B, C] 3 1 [A, B] [A, B] 2 2
[A, B, C, Z] 3 [A, B, C, Z] 3 [A, B] 2 以所有包含NFA的终止状态Z的DFA状态作为终止状态，得到DFA相应的状态转换图（以换名）如图7所示。
1 0 0 0 1 0 0 1 1 3 2 1
图7 正规表达式（0|1）*00的DFA
（3） 对该DFA进行最小化。
采用够造状态集划分的方法对DFA进行最小化，过程如下：
以知K={0，1，2，3}。首先将K分成两个子集 K1={0,1,2} （非终态集） K2={3} （终态集） 在K1={0,1,2}中，有
00=1∈K1 10=3∈K2 20=1∈K1 01=2∈K1 11=2∈K1 21=2∈K1