第一步：根据正规式构造NFA，先引入初始状态X和终止状态Y：
1(0∣1)*101 X Y
0 1 ε ε
再对该转换图进行分解，得到分解后的NFA如下图：
X 1 2 3 1 4 0 5 1 Y 1
第二步：对NFA进行确定化，获得状态转换矩阵： 状态 0 1 {X} ? {1，2，3} {1，2，3} {2，3} {2，3，4} {2，3} {2，3} {2，3，4} {2，3，4} {2，3，5} {2，3，4} {2，3，5} {2，3} {2，3，4，Y} {2，3，4，Y} {2，3，5} {2，3，4} 根据转换矩阵获得相应的DFA： 0 1 0 0 1 2 1 3 0 0 1 4 1 0 5 1 1 第三步：化简该DFA，获得最简的DFA即为所求。
首先根据是否终止状态将所有状态分为两个集合{0，1，2，3，4}和{5}，这里集合{5}已经不可划分，只需考虑集合{0，1，2，3，4}。
{0，1，2，3，4}0={2，4，-}，{0，1，2，3，4}1={1，3，5}
因为{1，3，5}和{2，4，-}不在一个集合里面，所以需要对集合{0，1，2，3，4}进行进一步的划分，检查其中的所有状态。状态0不能接受字符0，需要把状态0划分出来；另外，只有状态4读入字符1后进入状态5，因此将状态4划分出来，划分的结果为4个集合：{0}，{1，2，3}，{4}，{5}。
检查集合{1，2，3}，{1，2，3}0={2，4}，不属于同一个集合，因此要对集合{1，2，3}进行进一步划分，划分结果为5个集合：{0}，{1，2}，{3}，{4}，{5}。
检查集合{1，2}，{1，2}0={2}，{1，2}1=3，不需要进行进一步划分。所以最终划分结果为5个集合：{0}，{1，2}，{3}，{4}，{5}。 所以，最终所求DFA如下图示：
0 1 0 1 1 3 0 0 1 4 1 0 5 1
（2）、1(1010*∣1(010)*1)*0
（3）、0*10*10*10*
（4）、(00∣11)*((01∣10)(00∣11)*(01∣10)(00∣11)*)*
8、给出下面正规表达式：
（1） 以01结尾的二进制数串； （2） 能被5整除的十进制整数；
（3） 包含奇数个1或奇数个0的二进制数串；
（4） 英文字母组成的所有字符串，要求符号串中的字母依照字典序排列； （5） 没有重复出现的数字的数字符号串的全体；
（6） 最多有一个重复出现的数字的数字符号串的全体； （7） 不包含子串abb的由a和b组成的符号串的全体。 解：
（1）以01结尾的二进制数串； 分析题意，要求的是二进制数串，即由0和1构成的串，并且必须以01结尾，所以本题可以分两步完成：一部分实现由0和1构成的任意串，一部分即01，然后将它们连结在一起就可以了，所以所求为(1︱0)*01。 （2）能被5整除的十进制整数； 分析题意，本题要求的是十进制整数，也就是由0至9这10个数字组成的字符串，并且不能以0开头（整数“0”除外），要求能被5整除，则该串必须以0或者5结尾。根据分析，可以把本题分成两种情况考虑：一种情况时该整数只有一位，则该整数有0和5两种可能；另一种情况是该整数有多位，则该整数可以分成三部分考虑：一是第一位必须不为0；二是最后一位必须为0或5；三是中间部分可有可无，并且可以由0到9之间任意数字构成，所以所求为(1︱2︱3︱4︱5︱6︱7︱8︱9) (0︱1︱2︱3︱4︱5︱6︱7︱8︱9)*(0︱5)(0︱5)。
（3）包含奇数个1或奇数个0的二进制数串； 本题求二进制串，并且要求包含奇数个0或奇数个1，由于0和1都可
以在二进制串中任何地方出现，所以本题只需要考虑一种情况，另一种情况也可以类似求得。考虑包含奇数个0的字符串：由于只关心0的个数的奇偶数，我们可以把二进制串分成多段来考虑，第一段为二进制串的开始到第一个0为止，这一段包含一个0，并且0的前面有0个或多个1。对于剩下的二进制串按照每段包含两个0的方式去划分，即以0开始，以0结尾，中间可以有0个或多个1。如果一个二进制串被这样划分完后，剩下的部分如果全部是全1串（这些全1串在前面划分的串之间或最后），则该二进制串就有奇数个0，所以该二进制串可以这样描述：以第一段（1*0）开始，后面由全1串（1*）以及包含两个0的串（01*0）组成，所以包含奇数个0的正规表达式为1*0（1︱01*0）*。所以本题所求为1*0（1︱01*0）*︱0*1（0︱10*1）*。
（4）英文字母组成的所有字符串，要求符号串中的字母依照字典序排列；
（5）没有重复出现的数字的数字符号串的全体；
（6）最多有一个重复出现的数字的数字符号串的全体；
（7）不包含子串abb的由a和b组成的符号串的全体。
9、对下面情况给出DFA及正规表达式： （1）{0，1}上的含有子串010的所有串； （2）{0，1}上不含子串010的所有串。 解： （1）、 （2）、直接写出满足条件的正规表达式。考虑满足条件的字符串中的1：在串的开始部分可以有0个或多个1，串的尾部也可以有0个或多个1，但串的中间只要出现1则至少在两个以上，所以满足条件的正规表达式为1*(0∣111*)*1*。 所求的DFA如下图所示：
1 S 0A 1 1 B 0
10、 一个人带着狼、山羊和白菜在一条河的左岸。有一条船，大小正好能装下这个人和其他三件东西中的一件。人和他的随行物都要过到河的右岸。人每次只能将一件东西摆渡过河。但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉。类似地，若羊和白菜留下来无人照看，羊将会吃掉白菜。请问是否有可能渡过河去，使得羊和白菜都不被吃掉？如果可能，请用有限自
11、
12、
动机写出渡河的方法。 解：
将图3.18的（a）和（b）分别确定化和最小化。
a a，b 0 a (a)
1
a b 0 a a a b b 4 b 5 a
b b a
2 3 1 a (b)
解： （1）、图（a）中为一个NFA，所以需要先对它进行确定化，得到DFA，然后再对DFA进行最小化。
首先进行确定化，如下两个表所示： 状态 a b 状态 a b {0} {0，1} {1} 0 1 2 {0，1} {0，1} {1} 1 1 2 {1} {0} ? 2 0 根据状态转换矩阵得到如下图所示的DFA：
0 b a a 1 b a 2
化简后的DFA为：
a b a 0 2
（2）、题中所给即为一个DFA，不需要确定化，只对它进行最小化即可。 首先将状态划分为两个集合{{0，1}，{2，3，4，5}}。有{0，1}a={1}，{0，1}b={2，4}和{2，3，4，5}a={1，3，0，5}，{2，3，4，5}b={2，3，4，5}，所以可以进一步划分为{{0，1}，{2，4}，{3，5}}，然后有{0，1}a={1}，{0，1}b={2，4}，{2，4}a={1，0}，{2，4}b={3，5}，{3，5}a={3，5}，{3，5}b={2，4}。因此，最后划分结果是{{0，1}，{2，4}，{3，5}}。 最小化后的DFA如下图所示：
a ba bb a 1 2 0
13、 （1）给出描述C浮点数的DFA；
14、 构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。
分析：对这类题型的固定解法分4步进行：首先根据语言写出正规表达式；然后根据正规表达式构造相应的NFA；然后，对NFA进行确定化得到DFA；最后对DFA化简得到最简DFA。
第一步：写出正规表达式。根据题意，该DFA接受的字符串由0和1组成，并且每个1的后面都有0直接跟在右边，因此，可以将该字符串理解为由0和10构成的串，则相应的正规表达式就是(0︱10)*。 第二步：构造NFA。首先得出下图：
(0︱10)* X Y
然后对上图进行分解后得到如下图所示的NFA。