非确定性和Kleene定理.doc

语言与计算理论导引 非确定性和Kleene定理
4 非确定性和Kleene定理
4.1 非确定型有限自动机
为了证明正则语言等价于能够被FA识别的语言，我们先对FA作一些方便性的扩充。仍然具有有限的状态数，且识别语言的能力保持不变。一些限制放宽了，更容易构造和解释。
例子4.1图4-1a显示了例子3.14构造的FA，它接受的语言是(11+110)*0，图4-1b显示了一个不同于一般FA的例子，状态q4没有转移箭头，而状态q0在输入字符为1时有两个转移箭头。
状态 q4没有转移箭头，含义是不存在一个起始字符为a（本例为0或1）的输入字符串能够使得状态从q4转移到某个接受状态，我们可以增加一个失败（或死，dead）状态f，对于输入字符a，状态q4转移到f，失败状态的含义是只有进入没有离开的转移箭头。显然任何被成功接受的字符串都不会进入失败状态，因此为了简化图面，往往省略失败状态，而不会影响自动机的接受能力。
状态q0在同一个输入字符时有多个转移箭头，看起来是对传统FA的很大的突破。我们无法象传统FA机那样线性地记录字符串在FA中的转移过程，而在某些步骤出现了歧义，因此FA机要并行地运算各种可能。
但这种带多向转移的图似乎更适合正则表达式，比如图4-1b，从q0到q0有两个循环，一个表示的字符串是(11)*，另一个表示的是(110)*，综合起来，从q0到q0的字符串是(11+110)*，则从q0到q4的字符串是(11+110)*0。反过来，根据正则表达式(11+110)*0也能够很直观地画出相应的带多向转移的FA。
由于同一个字符串可能带来FA多个状态转移路径，因此现在问题变成，是否存在一条到达接受状态的路径，这类似于根据正则表达式生成字符串，某些步骤可以有多种尝试，只要其中一种尝试生成了字符串，则认为该字符串符合这个正则表达式。
因此这类FA给正则语言的分析引入了一个新的概念，即猜测尝试。现在不考虑这种具体实现的问题，而考虑如何形式化定义这类FA。我们只需要修改（或扩充）传统FA的转移函数的定义。传统的转移函数输入一个字符，转移到一个状态，即Q中的一个元素，例子4.1中的转移函数则转移到0个或多个状态，即Q的一个子集，包括空集。我们称这种转移函数是非确定的，而这样的FA称为非确定型FA（nondeterministic FA, NFA），而传统的FA称为确定型FA（deterministic FA, DFA）。目前我们看起来NFA比DFA要强大很多，以后将证明任何一个NFA都能构造一个完全模拟它的DFA，因此非确定型没有增强FA的能力。

定义4.1 非确定型有限自动机（NFA）是一个5元组，M=（Q, å, q0, d, A），Q和å是非空有限集，q0ÎQ，AÍQ，转移函数定义为：
d: Qxå®2Q
2Q是Q的幂集，即所有Q的子集组成的集合，则函数d的值从确定型的一个状态放松成一个状态集。

思考：初始状态可不可以由一个状态扩充成一个状态集？

类似地扩充连续转移函数（或称字符串的转移函数）d*的定义，其形式仍然是：
d*(p, xa) = d(d*(p, x), a)
自然想到用递归定义，首先，空串不影响状态变迁，但转移函数的值是一个集合，而不是单个状态，因此：
d*(p, L)={p}
而对于非空字符串x=a1a2...an，d*(p, x)的值也应该是一个集合，设qÎd*(p, x)，含义是存在一个状态路径：p0, p1, ..., pn，其中p0=p，pn=q，对每一个i，0<i<=n，当输入字符ai时，自动机能够从状态pi-1到达状态pi，即
piÎd*(pi-1, ai)

定义4.2a （NFA的d*函数的非递归定义）给定NFA M=（Q, å, q0, d, A），p是任意一个状态，则d*(p, L)=p，对于任意一个字符串x= a1a2...an，d*(p, x)是所有满足下面条件的状态q组成的集合。存在一个状态路径p0, p1, ..., pn，其中p0=p，pn=q，对每一个i，0<i<=n，满足：
piÎd*(pi-1, ai)

为了得到递归定义，令x=yan。根据定义4.2a，对于d*(p, x)的任意一个状态q，都存在d*(p, y)中的一个状态r，使得qÎd(r, an)。反过来，对于d*(p, y)中的任何一个状态r，d(r, an)的元素都属于d*(p, yan)，即可以递归定义如下：
d*(p, yan) = {q | qÎd(r, an)且rÎd*(p, y)}
进一步的简化形式见下面的定义4.2b。

定义4.2b （NFA的d*函数的递归定义）给定NFA M=（Q, å, q0, d, A），函数d*: Qxå*®2Q定义如下：
1. d*(q, L)={q}
2. d*(q, ya)=

显然，d*(q, a)= d(q, a)仍然成立，因此递归的起点实际上可以是长度为1的字符串。
定义4.3 NFA M=（Q, å, q0, d, A）接受字符串x的条件是d*(q0, x)ÇA¹f。M接受（或识别）的语言由所有被M接受的字符串组成，记为L(M)。一个语言L被M识别当且仅当L=L(M)。

例子4.2 M=（Q, å, q0, d, A），Q={q0, q1, q2, q3}，å={0, 1}，A={q3}，d的定义如下表：

q
d(q, 0)
d(q, 1)
q0
{q0}
{q0, q1}
q1
{q2}
{q2}
q2
{q3}
{q3}
q3
f
f

参见图4-2，现在要确定M接受的语言。
分析：对一些字符串计算d*(q0, x)，x的长度逐渐增加。首先计算长度为1的字符串（直接根据上面的转移表），
d*(q0, 0)={q0}，d*(q0, 0)={q0, q1}
d*(q0, 11)
d*(q0, 01)
d*(q0, 111)
d*(q0, 011)
见104页
M接受的语言的正则表达式是：{0, 1}*{1}{0, 1}2。这是我们在例子3.15中讲到的L3，右数第3个字符为1。参照图4-2的NFA，能够很容易地构造出接受语言Ln的、带n+1个状态的NFA。在例子3.14，我们说明了接受Ln的DFA至少需要2n个状态，这里显示了接受同样语言的NFA往往比最简单的DFA具有少得多的状态。
尽管NFA在概念上作了很有效的扩充，接受字符串的方式也简洁得多，但NFA接受语言的能力并没有增加，任何能被NFA接受的语言也能被DFA接受。我们将给出一个构造性证明，显示消除NFA的非确定性的通用方法，得到的DFA保持了NFA识别字符串的性质，因此识别同样的语言。我们知道NFA状态转移函数的结果是一个集合，而DFA相应结果是一个元素，因此将NFA转变成一个DFA的简单方法就是把集合看成一个更大集合（幂集）的元素，而原来的单个元素看成只有一个元素的集合，这种方法称为子集构造法（subset construction），DFA中的状态是NFA的状态集的子集。
这是一种类似空间换时间的方法，假设NFA的状态个数为n，则DFA的状态个数为2n（近似），但是DFA在识别一个长度为m的字符串时，只需要m次状态移动，设字母表共有k个字符，则NFA可能需要k+k2+...+km次状态转移，形成一个深度为m，宽度为k的搜索树。

定理4.1 对于任何一个NFA M接受的语言L，都存在一个DFA M接受。
证明：设NFA M={Q, å, q0, A, d}，则构造DFA M1={Q1, å, q1, A1, d1}如下：
Q1=2Q
q1={q0}
d1(q, a)=
A1={qÎQ1 | qÇA¹f}
最后一点揭示了NFA接受字符串x，只需要存在一条转移路径最终到达接受状态就可以了，不需要所有的转移路径都到达接受状态。为了证明NFA M和DFA M1接受同样的语言，只需证明下面一个事实，对任意的字符串x，
d1*(q1, x)= d*(q0, x)
注意此处d1*和d*定义的不同，d1是DFA的连续转移函数（参见定义3.3），d是NFA的连续转移函数（参见定义4.3），它将状态映射到状态集的子集。
证明：字符串x存在递归定义，因此可以在x上使用结构归纳法来证明。
1） 归纳基础，x=L，要证明d1*(q1, x)= d*(q0, x)。
d1*(q1, x) = d1*(q1, L) = q1 = {q0}
d*(q0, x) = d*(q0, L) = {q0}
因此，归纳基础成立。
2） 归纳推理，任给x，设d1*(q1, x)= d*(q0, x)，要证明d1*(q1, xa)= d*(q0, xa)。
d1*(q1, xa) = d1(d1*(q1, x), a) = d1(d*(q0, x), a) = = d*(q0, xa)
归纳推理成立，证明完毕。

字符串x被M接受，当且仅当d*(q0, x)ÇA¹f，当且仅当d1*(q1, x)ÇA¹f，当且仅当d1*(q1, x)ÎA1，当且仅当x被M1接受。定理4.1的证明提供了一个消除NFA非确定性的算法，我们用下面的例子说明这个算法。

例子4.3 给例子4.2给出的NFA构造相应的DFA。
分析：例子4.2给出的NFA共有4个状态，因此相应的DFA至多有16个状态，如果采用例子3.16的方法，只保留那些初始状态能够到达的状态，则状态数将大大减少。设相应的DFA M1={Q1, å, q1, A1, d1}，其中q1={q0}。则从初始状态出发，逐步构造DFA的状态和转移函数。
d1({q0}, 0) = {q0}
d1({q0}, 1) = {q0, q1} ---新状态
d1({q0, q1}, 0) = d(q0, 0)Èd(q1, 0) = {q0}È{q2} = {q0, q2} ---新状态
d1({q0, q1}, 1) = d(q0, 1)Èd(q1, 1) = {q0, q1}È{q2} = {q0, q1, q2} ---新状态
d1({q0, q2}, 0) = d(q0, 0)Èd(q2, 0) = {q0}È{q3} = {q0, q3} ---新状态
d1({q0, q2}, 1) = d(q0, 1)Èd(q2, 1) = {q0, q1}È{q3} = {q0, q1, q3} ---新状态
d1({q0, q1, q2}, 0) = ...
d1({q0, q1, q2}, 1) = ...
...
上面的过程可以用一个表来描述，这个表就是前面讲到的状态转移表。表中每一格对应上面的每一行计算式。

q
d(q, 0)
d(q, 1)
{q0}
{q0}
{q0, q1}
{q0, q1}
{q0, q2}
{q0, q1, q2}
{q0, q2}
{q0, q3}
{q0, q1, q3}
{q0, q1, q2}
...
...
...

整个过程可以用一个算法（程序）来完成，多次迭代，直到没有新状态产生才停止。而且能够保证根据这种方法构造的DFA是对应该NFA的最少状态DFA。参见图4-3。

问题：写出构造NFA的相应DFA的算法。

例子4.4 同样的方法可用来处理例子4.1b中NFA，计算得到的整个转移状态表如下：

q
d(q, 0)
d(q, 1)
{q0}
{q4}
{q1, q2}
{q4}
f
f
{q1, q2}
f
{q0, q3}
f
f
f
{q0, q3}
{q0, q4}
{q1, q2}
{q0, q4}
{q4}
{q1, q2}

如果用q0代替{q0}，p代替{q4}，r代替{q1, q2}，s代替f，t代替{q0, q3}，u代替{q0, q4}，则得到图4-1a。

4.2 带空转移的非确定型有限自动机
为了简化正则表达式和有限自动机的接受语言能力相当的证明，本节进一步扩充自动机的定义。下面例子显示了这种扩充的作用。

例子4.5 构造正则表达式E=0*(01)*的相应的有限自动机。
分析：显然容易构造0*和(01)*的FA，分别如图4-4a和图4-4b所示。现在考虑如何利用这两个FA完成整个FA的构造，即如何构造两个FA的连接运算。图4-4c给出了一个NFA，将这两个FA组合起来，能够接受语言L(E)。考虑的关键是给图4-4b的初始状态的添加初始字符。我们知道每个独立FA隐含的初始字符是空字符L，为了消除这个L，图4-4c增加了一条从q0到q2的连接两个FA的转移箭头。
上述方法在两个FA间添加的一些转移箭头很不直观、很不明显，不是一种很规范、可形式化的方法。为了简化两个FA的连接运算，我们允许NFA有更多猜测下一步状态的自由，即状态q0可以在未接受任何字符的情况下转移到q1，如图4-4d所示。前面显示了NFA的一个优点是比接受同样的语言的DFA需要少得多的状态数和更简洁的转移函数表，现在进一步放松条件后，新的NFA可能需要更少的状态数和转移箭头。

问题：状态q0能否和状态q1合并？

定义4.4 带空转移的NFA（记为NFA-L）是一个5元组M=（Q, å, q0, d, A），其中Q和å是非空有限集，q0ÎQ，AÍQ，转移函数定义为：
d: Qx(åÈ{L})®2Q

类似NFA的定义（参见定义4.1），我们需要扩展定义连续转移函数d，以便适用于NFA-L，它的基本思想是一致的，即d*(q, x)表示的是字符串在NFA-L中从状态q出发合法流动，最终停止在的状态。现在需要扩充定义的概念是“字符串在NFA-L中的合法流动”，或称为“NFA-L合法地处理字符串”。图4-5所示的简单例子可以说明这个概念。我们在字符串01中插入空字符L，得到0LL1L=x，显然x能够被图4-5所示NFA-L接受。

问题：在一个长度为n的字符串中插入L，可能的结果是，实际使用中将带来组合爆炸，不是可行的方法。

类似定义4.2a，我们给出定义4.5a。

定义4.5a （NFA-L的连续转移函数d*的非递归定义）任给一个NFA-L M=（Q, å, q0, d, A），p和q是属于Q的任意两个状态，任给一个å上的字符串x=a1a2...an，如果存在一个整数m>=n，序列b1, b2, ..., bmÎåÈ{L}满足b1b2...bm=x，存在一组状态p=p0, p1, ..., pm=q，对于每个1<=i<=m，都有piÎd(pi-1, bi)，则在字符串x驱动下，M的状态从p转移到q。
函数d*(p, x)的值是所有在x驱动下，从状态p转移到的所有状态组成的集合。

例如图4-5中，字符串01可以驱动状态从q0转移到f，字符串L可以驱动状态从r到t，或每个状态到自身。类似定义4.2b，我们给出递归定义，仍然利用字符串前缀计算的结果来定义整个字符串计算的结果，值得注意的是，我们还需要扩充递归基础的定义。显然d*(q, L)的结果不仅包含q，还应该包含从q出发经过L转移到达的其他状态。这里引入一个新的概念，空闭包（L-closure，空转移闭包），表示从某个状态（或状态集）出发经过一次或多次空转移到达的所有状态组成的集合。

定义4.6 状态集的空闭包（L-closure of a set of states），给定NFA-L M=（Q, å, q0, d, A），S是Q的子集，空闭包L(S)递归定义如下：
1. S中每个元素都是L(S)的元素；
2. 如果q是L(S)的元素，则d(q, L)中的每个元素都是L(S)的元素；
3. L(S)的元素只可能通过上面两步得到。

与大多数集合的递归定义不同的是，我们能够预先确定空闭包是一个有限集，因此可以将上面的递归定义转换成一个计算空闭包的算法（参见练习2.50）。规则1提供了初始值，规则2则提供了添加元素的方法，当L(S)不再增加时，则算法停止。
算法（计算L(S)），输入状态集S，输出S的空闭包，设为T。
1. T=S
2. 循环，直到T没有增加新元素
a) 循环，逐个检查T中的元素q，
T=TÈd(q, L)。

定义4.5b （NFA-L的连续转移函数d*的递归定义）给定一个NFA-L M=（Q, å, q0, d, A），连续转移函数d*: Qxå*®2Q定义如下：
1. d*(q, L) = L({q})
2. d*(q, ya) = L()

问题：对于DFA和NFA都有d*(q, a)= d(q, a)，但对于NFA-L，此式不成立。

对照定义4.2b，就是在NFA的连续转移函数计算的结果上，在进行一次空闭包计算。在识别字符串的过程中，每读入一个字符，每次状态转移都要计算一次空闭包。字符串x被NFA-L M接受的判定条件与NFA一致，当且仅当d*(q, x)ÇA¹f。所有被M接受的字符串组成被M接受的语言，记为L(M)。

例子4.6 考虑图4.6所示的NFA-L，我们显示如何计算空闭包和连续转移函数。
分析： L({s}) = L({s, w})
= L({s, w, q0})
= L({s, w, q0, p, t})
= L({s, w, q0, p, t}) ---没有新元素加入，计算结束
现在计算d*(q0, 010)，根据递归定义，需要计算d*(q0, 01)、d*(q0, 0)、d*(q0, L)，这里我们从底向上计算这组函数。
d*(q0, L) = L({q0})
= {q0, p, t}
d*(q0, 0) = L()
= L(d(q0, 0)Èd(p, 0)Èd(t, 0))
= L(fÈ{p}È{u})
= L({p, u})
= {p, u}
d*(q0, 01)= L()
= L(d(p, 1)Èd(u, 1))
= L({r})
= {r}
d*(q0, 010) = L()
= L(d(r, 0))
= L({s})
= {s, w, q0, p, t}
可见由于，d*(q0, 010)的结果含有w，w也是A的元素，因此字符串010被图4-6所示的NFA-L接受。另外，010的同等字符串是L010L，容易发现存在状态序列q0, p, p, r, s, w接受字符串L010L。
显然连续转移函数的定义提供了一种高效的算法来判定字符串是否被NFA-L接受，如果采用插入空字符，然后借用NFA的连续转移函数的计算方法，其时间复杂度为指数级。上述方法实际上是一种dynamic programming，Viterbi算法。

问题1：写出计算NFA-L的连续转移函数的算法。
问题2：上述方法判定字符串是否被NFA-L接受，它能否回答判定中隐含插入的空字符位置？或判定中哪一步用到了空转移？比如能否知道010，在第一步和最后步用到了空转移？
问题3：NFA-L可用于模糊查询，或两个字符串的模糊匹配，探寻如何在短的字符串中插入空字符，使得与长字符串达到最大匹配？

在4.1节我们说明了NFA接受语言的能力与DFA相当，现在我们要说明NFA-L接受语言的能力与NFA相当，即每个NFA-L能够找到一个接受能力相当的NFA。

定理4.2 对于任何一个NFA-L M=接受的语言L，都存在一个NFA M接受。（与定理4.1对比）
证明：设NFA-L M={Q, å, q0, A, d}，要构造NFA M1={Q1, å, q1, A1, d1}。
在定理4.1（为NFA构造相当的DFA）的证明中，我们通过重新定义状态集，从而消除了非确定性。NFA-L中的空转移也是一种非确定性，例如如果一个NFA-L中存在：
d(p, 0)=q
d(q, L)=r
则状态p在输入字符0时，有两个转移状态q和r。因此可以用类似d(p, 0)=r的式子代替d(q, L)=r，达到消除L的目的。显然凡是L(q)中的状态都可类似处理，即通过给空闭包中的每个状态添加转移箭头，就可以删除空转移。我们需要做的工作仅仅是消除一种特殊的非确定性情况。通用的方法如下。
Q1=Q
q1=q0
我们利用空闭包实现NFA的转移函数的构造。对于每个字符a，至多插入两个空字符（非连续的空字符，因为连续的空字符相当于一个空字符），写成LaL，因此在NFA-L中可能一个字符的转移至多两次涉及空闭包。
d1(q, a) = L()
由于
d*(q, a) = d*(q, La)
= L()
= L()
因此可以简写成
d1(q, a) = d*(q, a)

我们这样定义的目的是：对任意的状态q和字符串x，d1*(q, x)= d*(q, x)都成立。我们发现一个特例，当x=L时，除非我们重新构造Q1，否则无论怎么构造d1，都难以保证上式成立。所幸的是，对任意非空字符串x，上式成立。因此仅仅对A稍作修改，构造的A1，就能保证正确识别空串这个特例。
现在对字符串x实施结构归纳法来证明d1*(q, x)= d*(q, x)成立。
1. 归纳基础，x=a单个字符
d1*(q, a) = d1(q, a) [d1*是NFA的转移函数]= d*(q, a)
2. 归纳推理，设d1*(q, y)= d*(q, y)，
d1*(q, ya) =
=
=
而d*(q, ya) = L()，因此需要证明
= L()
=
= ---空闭包可移到外面
= ---d*(q, y)已经计算了空闭包，
因此可去掉一层空闭包。
=
现在我们证明构造NFA M1接受NFA-L M相同的语言，分两种情况讨论：
1. M中L({q0})ÇA¹f，此时A1=AÈ{q0}，对判定的字符串x分两种情况讨论
a) x=L
d*(q0, L)=L({q0})，而L({q0})ÇA¹f，被M接受
d1*(q0, L)=d1(q0, L)={q0}，而{q0}ÇA1={q0}¹f，被M1接受
因此L同时被M和M1接受。
b) x¹L
d1*(q0, x)=d*(q0, x)=B
要证明BÇA¹f当且仅当BÇA1¹f。分两种情况：
i. q0ÎB，则
L({q0})ÍB，由于
L({q0})ÇA¹f，因此
BÇA¹f，x被M接受
另外，A1=AÈ{q0}，因此
BÇA1¹f，x被M1接受
x被M和M1同时接受。
ii. q0ÏB，则
BÇA= BÇ(AÈ{q0})= BÇA1，因此
x要么同时被M和M1接受，要么同时被M和M1拒绝。
2. M中L({q0})ÇA=f，此时A1=A，对判定的字符串x分两种情况讨论
a) x=L
d*(q0, L)=L({q0})，而L({q0})ÇA=f，被M拒绝；
d1*(q0, L)=d1(q0, L)={q0}，因为L({q0})ÇA=f，则{q0}ÇA=f，A1=A，因此 {q0}ÇA1=f，被M1拒绝。
L同时被M和M1拒绝。
b) x¹L
d1*(q0, x)=d*(q0, x)=B，由于A1=A
因此BÇA¹f当且仅当BÇA1¹f，即x要么同时被M和M1接受，要么同时被拒绝。
上面讨论证明，任意一个字符串x，要么同时被M和M1接受，要么同时被拒绝。因此M和M1接受同样的语言。定理4.2证明完毕。

问题1：子集构造法能否类似定理4.1那样构造出相当的NFA？
问题2：直接从NFA-L构造DFA的算法？

NFA是DFA的更通用的模型，NFA-L是NFA的更通用模型，即我们可以说DFA是NFA的特殊情况，NFA是NFA-L的特殊情况。

定理4.1和定理4.2的结论可以用下面的定理4.3来总结。

定理4.3 对于字母表å上的任意语言L，下面三个命题是相当的
1. L可以被FA接受（此处FA就是DFA）
2. L可以被NFA接受
3. L可以被NFA-L接受
证明：根据定理4.1，2可以导出1；根据定理4.2，3可以导出2，现在只要证明1可以导出3。设L是FA M=(Q, S, q0, A, d)接受的语言，构造接受L的NFA-L M1=(Q, S, q0, A, d1)。仅仅需要重新定义转移函数，d1: Q´(SÈ{L})®2Q，
d1(q, L) = f
d1(q, a) = {d(q, a)}
容易证明M1与M接受相同的语言。

正如定理4.1，定理4.2的证明提供了一个消除NFA-L中空转移的算法，下面用两个例子来说明这个算法。这些例子也可用来作为消除非确定性的练习。

例子4.7 图4-7a给出了一个NFA-L M，它接受的语言是0*(01)*0*，下面表显示了M的转移函数和连续转移函数d*(q, 0)和d*(q, 1)的计算结果，这些结果可以用来构造相应的NFA M1。

q
d(q, L)
d(q, 0)
d(q, 1)
d*(q, 0)
d1(q, 0)
d*(q, 1)
d1(q, 1)
A
{B}
{A}
f
{A, B, C, D}
f
B
{D}
{C}
f
{C, D}
f
C
f
f
{B}
f
{B, D}
D
f
{D}
f
{D}
f

M=({A, B, C, D}, {0, 1}, A, {D}, d)
由于L({A})Ç{D}¹f，因此，
M1=({A, B, C, D}, {0, 1}, A, {A, D}, d1)，d1定义见上表。对图4-7a删除空转移，添加新转移，得到图4-7b，它表示的是相应的NFA。可以进一步消除NFA中的不确定性，得到相当的FA，如图4-7c所示。

例子4.8 图4-8a给出了一个NFA-L M，它接受的语言是0*((01)*1+1*0)，下标显示了它的转移函数和相当NFA的转移函数。

q
d(q, L)
d(q, 0)
d(q, 1)
d*(q, 0)
d1(q, 0)
d*(q, 1)
d1(q, 1)
A
{B, D}
{A}
f
{A, B, C, D, E}
{D, E}
B
f
{C}
{E}
{C}
{E}
C
f
f
{B}
f
{B}
D
f
{E}
{D}
{E}
{D}
E
f
f
f
f
f

根据上表得到的NFA如图4-8b所示，注意初始状态A不是接受状态，因为L({A})中没有接受状态。相当的FA如图4-8c所示。

4.3 Kleene定理
本章的前两节提供了证明定理3.1的数学工具，定理3.1称为Kleene定理，我们将其中的充分必要条件分成两部分来证明。

定理4.4 （Kleene定理第一部分）任何一个正则语言都存在一个有限自动机接受。
证明：根据定理4.3，我们只需要证明存在一个带空转移的非确定型有限自动机（NFA-L）接受这个正则表达式表示的语言。由于正则语言存在一个递归定义，而要证明的是正则语言的一个性质，因此很适合使用结构归纳法。先构造接受三种最基本的正则语言的NFA-L，然后构造接受三种正则语言运算的NFA-L。
1. 归纳基础，根据定义3.1，三种最基本的正则语言分别是：f、{L}和{a}，a是字母表S上的任意一个字符。参见图4-9。
2. 归纳推理，证明在正则语言的三种运算下保持性质，分别为这三种运算构造有限自动机。设接受语言L1和L2的NFA-L分别是：
M1=(Q1, S, q1, A1, d1)
M2=(Q2, S, q2, A2, d2)
不妨设Q1ÇQ2=f（如果必要，可以更改状态名字），现在分别构造接受L1ÈL2、L1L2和L1*的NFA-L Mu、Mc和Mk。
Mu=(Qu, S, qu, Au, du)，其中
qu是既不属于Q1，也不属于Q2的新状态；
Qu=Q1ÈQ2È{qu}；
Au=A1ÈA2

参见图4-10a，增加了一个新状态，和从新状态到M1和M2的初始状态的空转移，完成了一个分叉的构造。现在证明Mu接受的语言是L1ÈL2。一方面，任给一个字符串xÎL1ÈL2，则xÎL1或xÎL2，不妨设xÎL1，则M1接受x，即存在M1的一组状态，p1=q1, p2, ..., pnÎA1，接受x，由于从qu到q1是空转移，因此存在Mu的一组状态，qu, p1=q1, p2, ..., pnÎAu，接受x。另一方面，任给一个Mu接受的字符串x，即存在Mu的一组状态，qu, p1, p2, ..., pnÎAu，接受x，由于从qu只有两个空转移到q1或q2，不妨设p1=q1，Q1ÇQ2=f，因此p1, p2, ..., pn都在M1中，且pnÎA1，因此存在M1的一组状态p1, p2, ..., pn，接受x，即xÎL1ÈL2。

Mc=(Qc, S, qc, Ac, dc)，其中
Qc=Q1ÈQ2；
qc=q1;
Ac=A2;
---此为书上式子
或
---此为我的简化
参见图4-10b，增加了从M1的接收状态到M2的初始状态的空转移。设M1接受的字符串是x1，M2接受的字符串x2，则Mc接受的字符串是x1Lx2=x1x2。

Mk=(Qk, S, qk, Ak, dk)，其中
qk是不属于Q1的新状态；
Qk=Q1È{qk}；
Ak={qk}；

参见图4-10c，增加了一个新状态作为初始状态和唯一的接受状态，增加了从新状态到原初始状态的空转移，从原接收状态到新状态的空转移，完成了一个环的构造。设被M1接受的一组字符串是x1, x2, ..., xm，则字符串(Lx1L)(Lx2L)...(LxmL)=x1x2...xm能够被Mk接受。

因此在3种运算下，保持了正则语言能够被NFA-L接受的性质。证明完毕。

问题1：构造方法与定理3.4的区别。
问题2：构造对应多个语言的合并和连接的自动机。

以上证明提供了从正则表达式构造NFA-L的方法，这种方法构造的自动机不一定是最简的。

例子4.9 构造正则表达式r=(00+1)*(10)*的NFA-L。
分析：构成r的最基本的两个正则语言是{0}和{1}，它们对应的NFA-L如图4-11a所示。然后构造{00}和{10}的NFA-L，如图4-11b。图4-11c显示了{00+1}的NFA-L，图4-11d对应{00+1}*，图4-11e对应(10)*，最终得到的NFA-L如图4-11f所示。

严格按照定理4.4的算法构造的NFA-L往往有许多冗余的状态，图4-12给出了相应于图4-11的简化的NFA-L（参见练习4.35~4.37，简化NFA-L应该很小心）。尽管目前我们还没有简化NFA-L的形式化方法，但根据前两节的定理，我们知道如何将NFA-L转换成DFA，第5章将讲述化简DFA的形式化方法，因此最终存在一个简化自动机的方法。

定理4.5（Kleene定理第二部分）任何一个有限自动机接受的语言都是正则语言。
证明：设L是字母表å上非空转移的确定型有限自动机DFA M=(Q, S, q0, A, d)接受的语言，即L={xÎS* | d*(q0, x)ÎA}=。根据正则表达式定义，一组正则语言的并集仍然是正则语言，我们只需要证明下面一组语言是正则语言：
L(q0, q) = {xÎS* | d*(q0, x)=qÙqÎA}，
更一般地，我们证明对M的任意两个状态p和q，语言L(p, q) = {xÎS* | d*(p, x)=q }是正则语言。
很自然的证明方法是归纳法，比如根据L(p, q)中字符串的长度，或被接受的字符串从状态p到q所经过的状态数。这些方法也许不是很容易想到的有效方法，由于L(p, q)可以是无限集，则其中的字符串可以任意长，而且我们要证明的是整个语言的性质，而不是单个字符串的性质。因此根据经过的状态数是一种更好的归纳法。
现在我们假设M共有n个状态，并对每个状态编号，号码从1开始，到n结束。我们给出概念“经过状态s的路径”的形式化定义。给定一个字符串x，如果存在两个非空的字符串y和z，满足：
x=yz，d*(p, y)=s，d*(s, z)=q
则称x代表了一条从p到q，经过s的路径。注意根据我们的定义，起点和终点状态不能称为经过的状态，如上例，可以说经过了s，但不能说经过了p和q。
对于整数j>=0，L(p, q, j)表示所有从p到q，且经过状态的编号小于等于j的字符串组成的集合。由于M中状态的最大编号为n，显然L(p, q)中的字符串不会经过编号大于n的状态，因此L(p, q, n)=L(p, q)。
现在问题变成证明L(p, q, n)是正则语言。我们可以用数学归纳法证明对任意的0<=j<=n，L(p, q, j)都是正则语言。当然事实上，既然对任意的j>=n，L(p, q, j)=L(p, q, n)=L(p, q)，我们要证明的命题可以更通用，即对任意的j>=0，L(p, q, j)都是正则语言。
1. 归纳基础，j=0，证明L(p, q, 0)是正则语言。
既然M中状态的最小编号是1，L(p, q, 0)中的字符串表示的路径只能是从p直接到q，如果p¹q，则字符串是单个字母；如果p=q，还应包括空字符。空字符和单个字母都是正则语言，因此L(p, q, 0)是正则语言。
2. 归纳推理，设对每个k>=0，L(p, q, k)都是正则语言，证明L(p, q, k+1)也是正则语言。
由于k>=n时，L(p, q, k)= L(p, q, k+1)，此处仅证明k<n的情况。
L(p, q, k+1)的字符串表示的路径可分成两类，一种没有经过k+1号状态，即来自L(p, q, k)的元素；另一类经过了k+1号状态。只需证明第二类字符串组成的语言是正则语言。每个第二类字符串x可以分解成三部分yzw，y表示从p到k+1号状态的路径，z表示从k+1到k+1的路径，w表示从k+1到q的路径，因此
yÎL(p, k+1, k)
zÎL(k+1, k+1, k)* ---此处有起点和终点相同，存在循环，即Kleene*运算
wÎL(k+1, q, k)
因此，第二类字符串组成的语言是，
L(p, k+1, k) L(k+1, k+1, k)* L(k+1, q, k)，则
L(p, q, k+1)= L(p, q, k)+ L(p, k+1, k) L(k+1, k+1, k)* L(k+1, q, k)
根据正则语言的定义，正则语言的合并、连接和Kleene*运算后的结果仍然是正则语言。因此L(p, q, k+1)是正则语言，证明完毕。

定理4.5的证明提供了一个从有限自动机（确定型非空转移的有限自动机）导出相应正则表达式的方法，总结如下：

L(p, q, k+1)= L(p, q, k)+ L(p, k+1, k) L(k+1, k+1, k)* L(k+1, q, k)
L(p, q)=L(p, q, n)
L=

例子4.10 图4-14给出了一个FA，求它对应的正则表达式。
分析：我们用下表显示对应语言L(p, q, j)的正则表达式r(p, q, j)，0=<j<=2。

p
r(p, 1, 0)
r(p, 2, 0)
r(p, 3, 0)
1
a+L
b
f
2
a
L
b