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, δ, A），Q 和∑是非空有限集，q 0∈Q ，A ⊆Q ，转移函数定义为：
δ: Qx∑→2Q
2Q 是Q 的幂集，即所有Q 的子集组成的集合，则函数δ的值从确定型的一个状态放松成一个状态集。
思考：初始状态可不可以由一个状态扩充成一个状态集？
类似地扩充连续转移函数（或称字符串的转移函数）δ*的定义，其形式仍然是：
δ*(p, xa) = δ(δ*(p, x), a)
自然想到用递归定义，首先，空串不影响状态变迁，但转移函数的值是一个集合，而不是单个状态，因此：
δ*(p, Λ)={p}
而对于非空字符串x=a1a 2...a n ，δ*(p, x)的值也应该是一个集合，设q ∈δ*(p, x)，含义是存在一个状态路径：p 0, p1, ..., pn ，其中p 0=p，p n =q，对每一个i ，0
p i ∈δ*(pi-1, ai )
定义4.2a （NFA 的δ*函数的非递归定义）给定NFA M=（Q, ∑, q0, δ, A），p 是任意一个状态，则δ*(p, Λ)=p，对于任意一个字符串x= a1a 2...a n ，δ*(p, x)是所有满足下面条件的状态q 组成的集合。存在一个状态路径p 0, p1, ..., pn ，其中p 0=p，p n =q，对每一个i ，0
p i ∈δ*(pi-1, ai )
为了得到递归定义，令x=yan 。根据定义4.2a ，对于δ*(p, x)的任意一个状态q ，都存在δ*(p, y) 中的一个状态r ，使得q ∈δ(r, an ) 。反过来，对于δ*(p, y)中的任何一个状态r ，δ(r, an ) 的元素都属于δ*(p, yan ) ，即可以递归定义如下：
δ*(p, yan ) = {q | q∈δ(r, an ) 且r ∈δ*(p, y)} 进一步的简化形式见下面的定义4.2b 。
定义4.2b （NFA 的δ*函数的递归定义）给定NFA M=（Q, ∑, q0, δ, A），函数δ*: Qx∑*→2Q
定义如下：
1. δ*(q, Λ)={q} 2. δ*(q, ya)=
p ∈*(p , y )
⋃δ
δ(p , a )
显然，δ*(q, a)= δ(q, a)仍然成立，因此递归的起点实际上可以是长度为1的字符串。
定义4.3 NFA M=（Q, ∑, q0, δ, A）接受字符串x 的条件是δ*(q0, x)⋂A ≠φ。M 接受（或识别）的语言由所有被M 接受的字符串组成，记为L(M)。一个语言L 被M 识别当且仅当L=L(M)。
例子4.2 M=（Q, ∑, q0, δ, A），Q={q0, q1, q2, q3}，∑={0, 1}，A={q3}，δ的定义如下表：
参见图4-2，现在要确定M 接受的语言。
分析：对一些字符串计算δ*(q0, x)，x 的长度逐渐增加。首先计算长度为1的字符串（直接根据上面的转移表），
δ*(q0, 0)={q0}，δ*(q0, 0)={q0, q1}
δ*(q0, 11) δ*(q0, 01) δ*(q0, 111) δ*(q0, 011) 见104页
M 接受的语言的正则表达式是：{0, 1}*{1}{0, 1}2。这是我们在例子3.15中讲到的L 3，右数第3个字符为1。参照图4-2的NFA ，能够很容易地构造出接受语言L n 的、带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, δ}，则构造DFA M1={Q1, ∑, q1, A1, δ1}如下： Q 1=2Q q 1={q0}
δ1(q, a)=
⋃δ(q , a )
p ∈q
A 1={q∈Q 1 | q⋂A ≠φ} 最后一点揭示了NFA 接受字符串x ，只需要存在一条转移路径最终到达接受状态就可以了，不需要所有的转移路径都到达接受状态。为了证明NFA M和DFA M1接受同样的语言，只需证明下面一个事实，对任意的字符串x ，
δ1*(q1, x)= δ*(q0, x)
注意此处δ1*和δ*定义的不同，δ1是DFA 的连续转移函数（参见定义3.3），δ是NFA 的连续转移函数（参见定义4.3），它将状态映射到状态集的子集。
证明：字符串x 存在递归定义，因此可以在x 上使用结构归纳法来证明。 1） 归纳基础，x=Λ，要证明δ1*(q1, x)= δ*(q0, x)。 δ1*(q1, x) = δ1*(q1, Λ) = q1 = {q0} δ*(q0, x) = δ*(q0, Λ) = {q0} 因此，归纳基础成立。
2） 归纳推理，任给x ，设δ1*(q1, x)= δ*(q0, x)，要证明δ1*(q1, xa)= δ*(q0, xa)。
δ1*(q1, xa) = δ1(δ1*(q1, x), a) = δ1(δ*(q0, x), a) =
p ∈*(q 0, y )
⋃δ
δ(p , a ) = δ*(q0, xa)
归纳推理成立，证明完毕。
字符串x 被M 接受，当且仅当δ*(q0, x) ⋂A ≠φ，当且仅当δ1*(q1, x) ⋂A ≠φ，当且仅当δ1*(q1, x) ∈A 1，当且仅当x 被M 1接受。定理4.1的证明提供了一个消除NFA 非确定性的算法，我们用下面的例子说明这个算法。 例子4.3 给例子4.2给出的NFA 构造相应的DFA 。
分析：例子4.2给出的NFA 共有4个状态，因此相应的DFA 至多有16个状态，如果采用例子3.16的方法，只保留那些初始状态能够到达的状态，则状态数将大大减少。设相应的DFA M 1={Q1, ∑, q1, A1, δ1}，其中q1={q0}。则从初始状态出发，逐步构造DFA 的状态和转移函数。
δ1({q0}, 0) = {q0}
δ1({q0}, 1) = {q0, q1} ---新状态 δ1({q0, q1}, 0) = δ(q0, 0)⋃δ(q1, 0) = {q0}⋃{q2} = {q0, q2} ---新状态 δ1({q0, q1}, 1) = δ(q0, 1)⋃δ(q1, 1) = {q0, q1}⋃{q2} = {q0, q1, q2} ---新状态 δ1({q0, q2}, 0) = δ(q0, 0)⋃δ(q2, 0) = {q0}⋃{q3} = {q0, q3} ---新状态 δ1({q0, q2}, 1) = δ(q0, 1)⋃δ(q2, 1) = {q0, q1}⋃{q3} = {q0, q1, q3} ---新状态 δ1({q0, q1, q2}, 0) = ... δ1({q0, q1, q2}, 1) = ... ...
上面的过程可以用一个表来描述，这个表就是前面讲到的状态转移表。表中每一格对应上面的每一行计算式。
整个过程可以用一个算法（程序）来完成，多次迭代，直到没有新状态产生才停止。而且能够保证根据这种方法构造的DFA 是对应该NFA 的最少状态DFA 。参见图4-3。
问题：写出构造NFA 的相应DFA 的算法。
例子4.4 同样的方法可用来处理例子4.1b 中NFA ，计算得到的整个转移状态表如下：
如果用q0代替{q0}，p 代替{q4}，r 代替{q1, q2}，s 代替φ，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 隐含的初始字符是空字符Λ，为了消除这个Λ，图4-4c 增加了一条从q0到q2的连接两个FA 的转移箭头。
上述方法在两个FA 间添加的一些转移箭头很不直观、很不明显，不是一种很规范、可形式化的方法。为了简化两个FA 的连接运算，我们允许NFA 有更多猜测下一步状态的自由，即状态q0可以在未接受任何字符的情况下转移到q1，如图4-4d 所示。前面显示了NF A的一个优点是比接受同样的语言的DFA 需要少得多的状态数和更简洁的转移函数表，现在进一步放松条件后，新的NFA 可能需要更少的状态数和转移箭头。
问题：状态q0能否和状态q1合并？
定义4.4 带空转移的NFA （记为NFA-Λ）是一个5元组M=（Q, ∑, q0, δ, A），其中Q 和∑是非空有限集，q 0∈Q ，A ⊆Q ，转移函数定义为：
δ: Qx(∑⋃{Λ})→2Q
类似NFA 的定义（参见定义4.1），我们需要扩展定义连续转移函数δ，以便适用于NFA-Λ，它的基本思想是一致的，即δ*(q, x)表示的是字符串在NFA-Λ中从状态q 出发合法流动，最终停止在的状态。现在需要扩充定义的概念是“字符串在NFA-Λ中的合法流动”，或称为“NFA-Λ合法地处理字符串”。图4-5所示的简单例子可以说明这个概念。我们在字符串01中插入空字符Λ，得到0ΛΛ1Λ=x，显然x 能够被图4-5所示NFA-Λ接受。
2
问题：在一个长度为n 的字符串中插入Λ，可能的结果是C n ，实际使用中将带来组合爆炸，
不是可行的方法。
类似定义4.2a ，我们给出定义4.5a 。
定义4.5a （NFA-Λ的连续转移函数δ*的非递归定义）任给一个NFA-Λ M=（Q, ∑, q0, δ, A），p 和q 是属于Q 的任意两个状态，任给一个∑上的字符串x=a1a2...an，如果存在一个整数m>=n，序列b1, b2, ..., bm ∈∑⋃{Λ}满足b1b2...bm=x，存在一组状态p=p0, p1, ..., pm=q，对于每个1
函数δ*(p, x)的值是所有在x 驱动下，从状态p 转移到的所有状态组成的集合。
例如图4-5中，字符串01可以驱动状态从q0转移到f ，字符串Λ可以驱动状态从r 到t ，或每个状态到自身。类似定义4.2b ，我们给出递归定义，仍然利用字符串前缀计算的结果来定义整个字符串计算的结果，值得注意的是，我们还需要扩充递归基础的定义。显然δ*(q, Λ) 的结果不仅包含q ，还应该包含从q 出发经过Λ转移到达的其他状态。这里引入一个新的概念，空闭包（Λ-closure ，空转移闭包），表示从某个状态（或状态集）出发经过一次或多次空转移到达的所有状态组成的集合。
定义4.6 状态集的空闭包（Λ-closure of a set of states），给定NFA-Λ M=（Q, ∑, q0, δ, A），S 是Q 的子集，空闭包Λ(S)递归定义如下：
1. S 中每个元素都是Λ(S)的元素；
2. 如果q 是Λ(S)的元素，则δ(q, Λ) 中的每个元素都是Λ(S)的元素； 3. Λ(S)的元素只可能通过上面两步得到。
与大多数集合的递归定义不同的是，我们能够预先确定空闭包是一个有限集，因此可以将上面的递归定义转换成一个计算空闭包的算法（参见练习2.50）。规则1提供了初始值，规则2则提供了添加元素的方法，当Λ(S)不再增加时，则算法停止。
算法（计算Λ(S)），输入状态集S ，输出S 的空闭包，设为T 。 1. T=S
2. 循环，直到T 没有增加新元素
a) 循环，逐个检查T 中的元素q ，
T=T⋃δ(q, Λ) 。
定义4.5b （NFA-Λ的连续转移函数δ*的递归定义）给定一个NFA-Λ M=（Q, ∑, q0, δ, A），连续转移函数δ*: Qx∑*→2Q 定义如下：
1. δ*(q, Λ) = Λ({q})
2. δ*(q, ya) = Λ(
p ∈δ*(q , y )
⋃δ(p , a ) )
问题：对于DFA 和NFA 都有δ*(q, a)= δ(q, a)，但对于NFA-Λ，此式不成立。
对照定义4.2b ，就是在NFA 的连续转移函数计算的结果上，在进行一次空闭包计算。在识
别字符串的过程中，每读入一个字符，每次状态转移都要计算一次空闭包。字符串x 被NFA-Λ M 接受的判定条件与NFA 一致，当且仅当δ*(q, x)⋂A ≠φ。所有被M 接受的字符串组成被M 接受的语言，记为L(M)。 例子4.6 考虑图4.6所示的NFA-Λ，我们显示如何计算空闭包和连续转移函数。 分析： Λ({s}) = Λ({s, w})
= Λ({s, w, q0}) = Λ({s, w, q0, p, t}) = Λ({s, w, q0, p, t}) ---没有新元素加入，计算结束
现在计算δ*(q0, 010)，根据递归定义，需要计算δ*(q0, 01)、δ*(q0, 0)、δ*(q0, Λ) ，这里我们从底向上计算这组函数。
δ*(q0, Λ) = = δ*(q0, 0) =
= = = =
Λ({q0}) {q0, p, t} Λ(
p ∈δ*(q 0, Λ)
⋃δ(p , 0) )
Λ(δ(q0, 0)⋃δ(p, 0)⋃δ(t, 0)) Λ(φ⋃{p}⋃{u}) Λ({p, u}) {p, u} Λ(
p ∈δ*(q 0, 0)
δ*(q0, 01)=
= = =
⋃δ(p , 1) )
Λ(δ(p, 1)⋃δ(u, 1)) Λ({r}) {r} Λ(
p ∈δ*(q 0, 01)
δ*(q0, 010) =
⋃δ(p , 0) )
= Λ(δ(r, 0)) = Λ({s}) = {s, w, q0, p, t} 可见由于，δ*(q0, 010) 的结果含有w ，w 也是A 的元素，因此字符串010被图4-6所示的NFA-Λ接受。另外，010的同等字符串是Λ010Λ，容易发现存在状态序列q0, p, p, r, s, w接受字符串Λ010Λ。 显然连续转移函数的定义提供了一种高效的算法来判定字符串是否被NFA-Λ接受，如果采用插入空字符，然后借用NFA 的连续转移函数的计算方法，其时间复杂度为指数级。上述方法实际上是一种dynamic programming，Viterbi 算法。 问题1：写出计算NFA-Λ的连续转移函数的算法。 问题2：上述方法判定字符串是否被NFA-Λ接受，它能否回答判定中隐含插入的空字符位置？或判定中哪一步用到了空转移？比如能否知道010，在第一步和最后步用到了空转移？ 问题3：NFA-Λ可用于模糊查询，或两个字符串的模糊匹配，探寻如何在短的字符串中插入空字符，使得与长字符串达到最大匹配？
在4.1节我们说明了NFA 接受语言的能力与DFA 相当，现在我们要说明NFA-Λ接受语言的能力与NFA 相当，即每个NFA-Λ能够找到一个接受能力相当的NFA 。
定理4.2 对于任何一个NFA-Λ M=接受的语言L ，都存在一个NFA M 接受。（与定理4.1对比）
证明：设NFA-Λ M={Q, ∑, q0, A, δ}，要构造NFA M1={Q1, ∑, q1, A1, δ1}。
在定理4.1（为NFA 构造相当的DFA ）的证明中，我们通过重新定义状态集，从而消除了非确定性。NFA-Λ中的空转移也是一种非确定性，例如如果一个NFA-Λ中存在：
δ(p, 0)=q δ(q, Λ)=r
则状态p 在输入字符0时，有两个转移状态q 和r 。因此可以用类似δ(p, 0)=r的式子代替δ(q, Λ)=r，达到消除Λ的目的。显然凡是Λ(q)中的状态都可类似处理，即通过给空闭包中的每个状态添加转移箭头，就可以删除空转移。我们需要做的工作仅仅是消除一种特殊的非确定性情况。通用的方法如下。
Q1=Q q1=q0
我们利用空闭包实现NFA 的转移函数的构造。对于每个字符a ，至多插入两个空字符（非连续的空字符，因为连续的空字符相当于一个空字符），写成Λa Λ，因此在NFA-Λ中可能一个字符的转移至多两次涉及空闭包。
δ1(q, a) = Λ(
p ∈Λ({q })
⋃δ(p , a ) )
由于
δ*(q, a) = δ*(q, Λa)
= Λ(= Λ(
p ∈δ*(q , Λ)
⋃δ(p , a ) )
p ∈Λ({q })
⋃δ(p , a ) )
因此可以简写成 δ1(q, a) = δ*(q, a)
⎧A ⋃{q 0}A 1=⎨
⎩A
如果Λ({q 0})⋂A ≠φ否则
我们这样定义的目的是：对任意的状态q 和字符串x ，δ1*(q, x)= δ*(q, x)都成立。我们发现一个特例，当x=Λ时，除非我们重新构造Q1，否则无论怎么构造δ1，都难以保证上式成立。所幸的是，对任意非空字符串x ，上式成立。因此仅仅对A 稍作修改，构造的A 1，就能保证正确识别空串这个特例。
现在对字符串x 实施结构归纳法来证明δ1*(q, x)= δ*(q, x)成立。 1. 归纳基础，x=a单个字符
δ1*(q, a) = δ1(q, a) [δ1*是NFA 的转移函数]= δ*(q, a) 2. 归纳推理，设δ1*(q, y)= δ*(q, y)，
δ1*(q, ya) =
= =
p ∈δ1*(q , y )
⋃
δ1(p , a )
p ∈δ*(q , y )
⋃
δ1(p , a )
p ∈δ(q , y )
⋃*
δ*(p , a )
δ(p , a ) ) ，因此需要证明
p ∈δ*(q , y )
而δ*(q, ya) = Λ(
p ∈δ*(q , y )
⋃
p ∈δ(q , y )
⋃*⋃*
δ*(p , a ) = Λ(δ*(p , a ) =
⋃δ(p , a ) )
p ∈δ(q , y ) p ∈δ
⋃*
Λ⎛ ⋃δ(r , a ) ⎫⎪
(q , y ) ⎝r ∈Λ({p })⎭
---空闭包可移到外面
= Λ
⎛⋃⎛⋃δ(r , a ) ⎫⎫
⎪⎪
⎭⎭⎝p ∈δ*(q , y ) ⎝r ∈Λ({p })
⎛⋃⎛⋃δ(r , a ) ⎫⎫
⎪⎪*r ∈{p }p ∈δ(q , y ) ⎝⎭⎭⎝
= Λ
---δ*(q, y)已经计算了空闭包， 因此可去掉一层空闭包。
= Λ
⎛⋃δ(p , a ) ⎫
⎪
⎝p ∈δ*(q , y ) ⎭
现在我们证明构造NFA M1接受NFA-Λ M相同的语言，分两种情况讨论：
1. M 中Λ({q0})⋂A ≠φ，此时A1=A⋃{q0}，对判定的字符串x 分两种情况讨论
a) x=Λ
δ*(q0, Λ)=Λ({q0})，而Λ({q0})⋂A ≠φ，被M 接受
δ *(q0, Λ)=δ (q0, Λ)={q0}，而{q0}⋂A1={q0}≠φ，被M1接受 因此Λ同时被M 和M1接受。 b) x ≠Λ
δ *(q0, x)=δ*(q0, x)=B
要证明B ⋂A ≠φ当且仅当B ⋂A1≠φ。分两种情况： i. q0∈B ，则
Λ({q0})⊆B ，由于 Λ({q0})⋂A ≠φ，因此 B ⋂A ≠φ，x 被M 接受 另外，A1=A⋃{q0}，因此 B ⋂A1≠φ，x 被M1接受 x 被M 和M1同时接受。 ii. q0∉B ，则
B ⋂A= B⋂(A⋃{q0})= B⋂A1，因此
x 要么同时被M 和M1接受，要么同时被M 和M1拒绝。
2. M 中Λ({q0})⋂A=φ，此时A1=A，对判定的字符串x 分两种情况讨论
a) x=Λ
δ*(q0, Λ)=Λ({q0})，而Λ({q0})⋂A=φ，被M 拒绝；
δ *(q0, Λ)=δ (q0, Λ)={q0}，因为Λ({q0})⋂A=φ，则{q0}⋂A=φ，A1=A，因此 {q0}⋂A1=φ，被M1拒绝。
Λ同时被M 和M1拒绝。 b) x ≠Λ
δ *(q0, x)=δ*(q0, x)=B ，由于A1=A
因此B ⋂A ≠φ当且仅当B ⋂A1≠φ，即x 要么同时被M 和M1接受，要么同时被拒绝。
上面讨论证明，任意一个字符串x ，要么同时被M 和M1接受，要么同时被拒绝。因此M 和M1接受同样的语言。定理4.2证明完毕。
问题1：子集构造法能否类似定理4.1那样构造出相当的NFA ？ 问题2：直接从NFA-Λ构造DFA 的算法？
NFA 是DFA 的更通用的模型，NFA-Λ是NFA 的更通用模型，即我们可以说DFA 是NFA 的特殊情况，NFA 是NFA-Λ的特殊情况。
定理4.1和定理4.2的结论可以用下面的定理4.3来总结。
定理4.3 对于字母表∑上的任意语言L ，下面三个命题是相当的 1. L 可以被FA 接受（此处FA 就是DFA ） 2. L 可以被NFA 接受 3. L 可以被NFA-Λ接受
证明：根据定理4.1，2可以导出1；根据定理4.2，3可以导出2，现在只要证明1可以导出3。设L 是FA M=(Q, ∑, q0, A, δ) 接受的语言，构造接受L 的NFA-Λ M1=(Q, ∑, q0, A, δ1) 。仅仅需要重新定义转移函数，δ1: Q⨯(∑⋃{Λ})→2Q ，
δ1(q, Λ) = φ
δ1(q, a) = {δ(q, a)} 容易证明M1与M 接受相同的语言。 正如定理4.1，定理4.2的证明提供了一个消除NFA-Λ中空转移的算法，下面用两个例子来说明这个算法。这些例子也可用来作为消除非确定性的练习。
例子4.7 图4-7a 给出了一个NFA-Λ M，它接受的语言是0*(01)*0*，下面表显示了M 的转移函数和连续转移函数δ*(q, 0)和δ*(q, 1)的计算结果，这些结果可以用来构造相应的NFA M1。
M=({A, B, C, D}, {0, 1}, A, {D}, δ) 由于Λ({A})⋂{D}≠φ，因此，
M1=({A, B, C, D}, {0, 1}, A, {A, D}, δ1) ，δ1定义见上表。对图4-7a 删除空转移，添加新转移，得到图4-7b ，它表示的是相应的NFA 。可以进一步消除NFA 中的不确定性，得到相当的FA ，如图4-7c 所示。
例子4.8 图4-8a 给出了一个NFA-Λ M，它接受的语言是0*((01)*1+1*0)，下标显示了它的转移函数和相当NFA 的转移函数。
根据上表得到的NFA 如图4-8b 所示，注意初始状态A 不是接受状态，因为Λ({A})中没有接受状态。相当的FA 如图4-8c 所示。
4.3 Kleene 定理
本章的前两节提供了证明定理3.1的数学工具，定理3.1称为Kleene 定理，我们将其中的充分必要条件分成两部分来证明。
定理4.4 （Kleene 定理第一部分）任何一个正则语言都存在一个有限自动机接受。
证明：根据定理4.3，我们只需要证明存在一个带空转移的非确定型有限自动机（NFA-Λ）接受这个正则表达式表示的语言。由于正则语言存在一个递归定义，而要证明的是正则语言的一个性质，因此很适合使用结构归纳法。先构造接受三种最基本的正则语言的NFA-Λ，然后构造接受三种正则语言运算的NFA-Λ。
1. 归纳基础，根据定义3.1，三种最基本的正则语言分别是：φ、{Λ}和{a}，a 是字母表∑
上的任意一个字符。参见图4-9。
2. 归纳推理，证明在正则语言的三种运算下保持性质，分别为这三种运算构造有限自动
机。设接受语言L1和L2的NFA-Λ分别是： M1=(Q1, ∑, q1, A1, δ1) M2=(Q2, ∑, q2, A2, δ2)
不妨设Q1⋂Q2=φ（如果必要，可以更改状态名字），现在分别构造接受L 1⋃L 2、L 1L 2和L 1*的NFA-Λ Mu 、M c 和M k 。 M u =(Qu , ∑, qu , Au , δu ) ，其中
q u 是既不属于Q1，也不属于Q2的新状态； Q u =Q1⋃Q2⋃{qu }； A u =A1⋃A2
⎧{q 1, q 2}q =q u ∧a =Λ⎪φq =q u ∧a ≠Λ⎪
δu (q , a ) =⎨
q ∈Q 1
⎪δ1(q , a ) ⎪q ∈Q 2⎩δ2(q , a )
参见图4-10a ，增加了一个新状态，和从新状态到M1和M2的初始状态的空转移，完
成了一个分叉的构造。现在证明M u 接受的语言是L1⋃L 2。一方面，任给一个字符串x ∈L1⋃L 2，则x ∈L1或x ∈L2，不妨设x ∈L1，则M1接受x ，即存在M1的一组状态，p1=q1, p2, ..., pn∈A1，接受x ，由于从q u 到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=φ，因此p1, p2, ..., pn 都在M1中，且pn ∈A1，因此存在M1的一组状态p1, p2, ..., pn，接受x ，即x ∈L1⋃L 2。
Mc=(Qc , ∑, qc , Ac , δc ) ，其中 Q c =Q1⋃Q2； qc=q1; Ac=A2;
q ∈A 1∧a ≠Λ⎧δ1(q , a )
⎪δ(q , a ) ⋃{q }q ∈A ∧a =Λ⎪21
δc (q , a ) =⎨1
δ(q , a ) q ∈Q ∧q ∉A 111⎪⎪q ∈Q 2⎩δ2(q , a )
或
---此为书上式子
⎧δ1(q , Λ) ⋃{q 2}q ∈A 1∧a =Λ⎪
δc (q , a ) =⎨δ1(q , a ) q ∈Q 1
⎪δ(q , a ) q ∈Q 22⎩
---此为我的简化
参见图4-10b ，增加了从M1的接收状态到M2的初始状态的空转移。设M1接受的字
符串是x1，M2接受的字符串x2，则Mc 接受的字符串是x1Λx2=x1x2。
M k =(Qk , ∑, qk , Ak , δk ) ，其中 qk 是不属于Q1的新状态； Qk=Q1⋃{qk}； Ak={qk}；
{q 1}q =q k ∧a =Λ⎧⎪
δk (q , a ) =⎨δ1(q , Λ) ⋃{q k }q ∈A 1∧a =Λ
⎪δ(q , a ) (q ∈Q 1∧q ∉A 1) ∨(q ∈A 1∧a ≠Λ) 1⎩
参见图4-10c ，增加了一个新状态作为初始状态和唯一的接受状态，增加了从新状态到
原初始状态的空转移，从原接收状态到新状态的空转移，完成了一个环的构造。设被M1接受的一组字符串是x1, x2, ..., xm，则字符串(Λx1Λ)(Λx2Λ)...(Λxm Λ)=x1x2...xm能够被Mk 接受。
因此在3种运算下，保持了正则语言能够被NFA-Λ接受的性质。证明完毕。
问题1：构造方法与定理3.4的区别。
问题2：构造对应多个语言的合并和连接的自动机。
以上证明提供了从正则表达式构造NFA-Λ的方法，这种方法构造的自动机不一定是最简的。
例子4.9 构造正则表达式r=(00+1)*(10)*的NFA-Λ。
分析：构成r 的最基本的两个正则语言是{0}和{1}，它们对应的NFA-Λ如图4-11a 所示。然后构造{00}和{10}的NFA-Λ，如图4-11b 。图4-11c 显示了{00+1}的NFA-Λ，图4-11d 对应{00+1}*，图4-11e 对应(10)*，最终得到的NFA-Λ如图4-11f 所示。
严格按照定理4.4的算法构造的NFA-Λ往往有许多冗余的状态，图4-12给出了相应于图4-11的简化的NFA-Λ（参见练习4.35~4.37，简化NFA-Λ应该很小心）。尽管目前我们还没有简化NFA-Λ的形式化方法，但根据前两节的定理，我们知道如何将NFA-Λ转换成DFA ，第5章将讲述化简DFA 的形式化方法，因此最终存在一个简化自动机的方法。
定理4.5（Kleene 定理第二部分）任何一个有限自动机接受的语言都是正则语言。 证明：设L 是字母表∑上非空转移的确定型有限自动机DFA M=(Q, ∑, q0, A, δ) 接受的语言，即L={x∈∑* | δ*(q0, x)∈A}=⋃{x ∈∑*|δ*(q 0, x ) =q }。根据正则表达式定义，一组正则语言
q ∈A
的并集仍然是正则语言，我们只需要证明下面一组语言是正则语言： L(q0, q) = {x∈∑* | δ*(q0, x)=q∧q ∈A}，
更一般地，我们证明对M 的任意两个状态p 和q ，语言L(p, q) = {x∈∑* | δ*(p, x)=q }是正则语言。
很自然的证明方法是归纳法，比如根据L(p, q)中字符串的长度，或被接受的字符串从状态p 到q 所经过的状态数。这些方法也许不是很容易想到的有效方法，由于L(p, q)可以是无限集，则其中的字符串可以任意长，而且我们要证明的是整个语言的性质，而不是单个字符串的性质。因此根据经过的状态数是一种更好的归纳法。
现在我们假设M 共有n 个状态，并对每个状态编号，号码从1开始，到n 结束。我们给出概念“经过状态s 的路径”的形式化定义。给定一个字符串x ，如果存在两个非空的字符串y 和z ，满足：
x=yz，δ*(p, y)=s，δ*(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=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
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的证明提供了一个从有限自动机（确定型非空转移的有限自动机）导出相应正则表达式的方法，总结如下：
p ≠q ⎧{a ∈∑|δ(p , a ) =q }
L (p , q , 0) =⎨
{a ∈∑|δ(p , a ) =q }⋃{Λ}p =q ⎩
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=⋃L (q 0, q )
q ∈A
例子4.10 图4-14给出了一个FA ，求它对应的正则表达式。
分析：我们用下表显示对应语言L(p, q, j)的正则表达式r(p, q, j)，0=
上表在计算中，用到了一些简化方法，如：
r(1, 3, 1)=r(1, 3, 0) + r(1, 1, 0)r(1, 1, 0)*r(1, 3, 0)= φ
其中r(1, 3, 0)=φ，而空集与其他任何集合的连接运算结果仍是空集。 r(3, 2, 1) = r(3, 2, 0)+r(3, 1, 0)r(1,1,0)*r(1,2,0) = b+a(a+Λ)*b = Λb+a+b
= a*b
r(1,1,2) = r(1,1,1)+r(1,2,1)r(2,2,1)*r(2,1,1) = a* + a*b(a+b)*a+ = a* + a*(ba+)*ba+ = a* + a*(ba+) + = a*(ba+)* r(3,2,3) = r(3,2,1)+r(3,2,1)r(2,2,1)*r(2,2,1) = a*b + a*b(a+b)*(Λ+a+b) = a*b + a*b(a+b)*
= a*b(a+b)*
接受状态是1和2，因此要求的正则表达式r=r(1,1,3)+r(1,2,3)。 r(1,1,3) = r(1,1,2)+r(1,3,2)r(3,3,2)*r(3,1,2) = a*(ba+)*+a*(ba+)*bb(Λ+a*b(a+b)*b)*(a++a*(ba+) +) = a*(ba+)*+a*(ba+)*bb(a*(ba+)*bb)*(a++a*(ba+) +)
= a*(ba+)*+(a*(ba+)*bb)+(a++a*(ba+) +)
r(1,2,3) r
= r(1,2,2)+r(1,3,2)r(3,3,2)*r(3,2,2)
= a*(ba+)*b+a*(ba+)*bb(a*b(a+b)*b)*a*b(a+b)* = a*(ba+)*b+a*(ba+)*bb(a*(ba+)*bb)*a*b(a+b)* = a*(ba+)*b+(a*(ba+)*bb)+a*(ba+)*b = (a*(ba+)*bb)* a*(ba+)*b
= r(1,1,3)+r(1,2,3)
= a*(ba+)*+(a*(ba+)*bb)+(a++a*(ba+) +)+(a*(ba+)*bb)*a*(ba+)*b = a*(ba+)*+(a*(ba+)*bb)*(a*(ba+)*bb(a++a*(ba+) +)+a*(ba+)*b = a*(ba+)*+(a*(ba+)*bb)*a*(ba+)*(bba++bba*(ba+) ++b)
尽管希望能够进一步简化，但没有一个好的形式化方法。
问题：状态与字符串的关系。给定一个FA ，字符串与状态序列（或称路径）是一一对应关系，容易找到从字符串导出状态的方法，从状态导出字符串的方法。如果是NFA 呢？如果是NFA- 呢？
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, δ, A），Q 和∑是非空有限集，q 0∈Q ，A ⊆Q ，转移函数定义为：
δ: Qx∑→2Q
2Q 是Q 的幂集，即所有Q 的子集组成的集合，则函数δ的值从确定型的一个状态放松成一个状态集。
思考：初始状态可不可以由一个状态扩充成一个状态集？
类似地扩充连续转移函数（或称字符串的转移函数）δ*的定义，其形式仍然是：
δ*(p, xa) = δ(δ*(p, x), a)
自然想到用递归定义，首先，空串不影响状态变迁，但转移函数的值是一个集合，而不是单个状态，因此：
δ*(p, Λ)={p}
而对于非空字符串x=a1a 2...a n ，δ*(p, x)的值也应该是一个集合，设q ∈δ*(p, x)，含义是存在一个状态路径：p 0, p1, ..., pn ，其中p 0=p，p n =q，对每一个i ，0
p i ∈δ*(pi-1, ai )
定义4.2a （NFA 的δ*函数的非递归定义）给定NFA M=（Q, ∑, q0, δ, A），p 是任意一个状态，则δ*(p, Λ)=p，对于任意一个字符串x= a1a 2...a n ，δ*(p, x)是所有满足下面条件的状态q 组成的集合。存在一个状态路径p 0, p1, ..., pn ，其中p 0=p，p n =q，对每一个i ，0
p i ∈δ*(pi-1, ai )
为了得到递归定义，令x=yan 。根据定义4.2a ，对于δ*(p, x)的任意一个状态q ，都存在δ*(p, y) 中的一个状态r ，使得q ∈δ(r, an ) 。反过来，对于δ*(p, y)中的任何一个状态r ，δ(r, an ) 的元素都属于δ*(p, yan ) ，即可以递归定义如下：
δ*(p, yan ) = {q | q∈δ(r, an ) 且r ∈δ*(p, y)} 进一步的简化形式见下面的定义4.2b 。
定义4.2b （NFA 的δ*函数的递归定义）给定NFA M=（Q, ∑, q0, δ, A），函数δ*: Qx∑*→2Q
定义如下：
1. δ*(q, Λ)={q} 2. δ*(q, ya)=
p ∈*(p , y )
⋃δ
δ(p , a )
显然，δ*(q, a)= δ(q, a)仍然成立，因此递归的起点实际上可以是长度为1的字符串。
定义4.3 NFA M=（Q, ∑, q0, δ, A）接受字符串x 的条件是δ*(q0, x)⋂A ≠φ。M 接受（或识别）的语言由所有被M 接受的字符串组成，记为L(M)。一个语言L 被M 识别当且仅当L=L(M)。
例子4.2 M=（Q, ∑, q0, δ, A），Q={q0, q1, q2, q3}，∑={0, 1}，A={q3}，δ的定义如下表：
参见图4-2，现在要确定M 接受的语言。
分析：对一些字符串计算δ*(q0, x)，x 的长度逐渐增加。首先计算长度为1的字符串（直接根据上面的转移表），
δ*(q0, 0)={q0}，δ*(q0, 0)={q0, q1}
δ*(q0, 11) δ*(q0, 01) δ*(q0, 111) δ*(q0, 011) 见104页
M 接受的语言的正则表达式是：{0, 1}*{1}{0, 1}2。这是我们在例子3.15中讲到的L 3，右数第3个字符为1。参照图4-2的NFA ，能够很容易地构造出接受语言L n 的、带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, δ}，则构造DFA M1={Q1, ∑, q1, A1, δ1}如下： Q 1=2Q q 1={q0}
δ1(q, a)=
⋃δ(q , a )
p ∈q
A 1={q∈Q 1 | q⋂A ≠φ} 最后一点揭示了NFA 接受字符串x ，只需要存在一条转移路径最终到达接受状态就可以了，不需要所有的转移路径都到达接受状态。为了证明NFA M和DFA M1接受同样的语言，只需证明下面一个事实，对任意的字符串x ，
δ1*(q1, x)= δ*(q0, x)
注意此处δ1*和δ*定义的不同，δ1是DFA 的连续转移函数（参见定义3.3），δ是NFA 的连续转移函数（参见定义4.3），它将状态映射到状态集的子集。
证明：字符串x 存在递归定义，因此可以在x 上使用结构归纳法来证明。 1） 归纳基础，x=Λ，要证明δ1*(q1, x)= δ*(q0, x)。 δ1*(q1, x) = δ1*(q1, Λ) = q1 = {q0} δ*(q0, x) = δ*(q0, Λ) = {q0} 因此，归纳基础成立。
2） 归纳推理，任给x ，设δ1*(q1, x)= δ*(q0, x)，要证明δ1*(q1, xa)= δ*(q0, xa)。
δ1*(q1, xa) = δ1(δ1*(q1, x), a) = δ1(δ*(q0, x), a) =
p ∈*(q 0, y )
⋃δ
δ(p , a ) = δ*(q0, xa)
归纳推理成立，证明完毕。
字符串x 被M 接受，当且仅当δ*(q0, x) ⋂A ≠φ，当且仅当δ1*(q1, x) ⋂A ≠φ，当且仅当δ1*(q1, x) ∈A 1，当且仅当x 被M 1接受。定理4.1的证明提供了一个消除NFA 非确定性的算法，我们用下面的例子说明这个算法。 例子4.3 给例子4.2给出的NFA 构造相应的DFA 。
分析：例子4.2给出的NFA 共有4个状态，因此相应的DFA 至多有16个状态，如果采用例子3.16的方法，只保留那些初始状态能够到达的状态，则状态数将大大减少。设相应的DFA M 1={Q1, ∑, q1, A1, δ1}，其中q1={q0}。则从初始状态出发，逐步构造DFA 的状态和转移函数。
δ1({q0}, 0) = {q0}
δ1({q0}, 1) = {q0, q1} ---新状态 δ1({q0, q1}, 0) = δ(q0, 0)⋃δ(q1, 0) = {q0}⋃{q2} = {q0, q2} ---新状态 δ1({q0, q1}, 1) = δ(q0, 1)⋃δ(q1, 1) = {q0, q1}⋃{q2} = {q0, q1, q2} ---新状态 δ1({q0, q2}, 0) = δ(q0, 0)⋃δ(q2, 0) = {q0}⋃{q3} = {q0, q3} ---新状态 δ1({q0, q2}, 1) = δ(q0, 1)⋃δ(q2, 1) = {q0, q1}⋃{q3} = {q0, q1, q3} ---新状态 δ1({q0, q1, q2}, 0) = ... δ1({q0, q1, q2}, 1) = ... ...
上面的过程可以用一个表来描述，这个表就是前面讲到的状态转移表。表中每一格对应上面的每一行计算式。
整个过程可以用一个算法（程序）来完成，多次迭代，直到没有新状态产生才停止。而且能够保证根据这种方法构造的DFA 是对应该NFA 的最少状态DFA 。参见图4-3。
问题：写出构造NFA 的相应DFA 的算法。
例子4.4 同样的方法可用来处理例子4.1b 中NFA ，计算得到的整个转移状态表如下：
如果用q0代替{q0}，p 代替{q4}，r 代替{q1, q2}，s 代替φ，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 隐含的初始字符是空字符Λ，为了消除这个Λ，图4-4c 增加了一条从q0到q2的连接两个FA 的转移箭头。
上述方法在两个FA 间添加的一些转移箭头很不直观、很不明显，不是一种很规范、可形式化的方法。为了简化两个FA 的连接运算，我们允许NFA 有更多猜测下一步状态的自由，即状态q0可以在未接受任何字符的情况下转移到q1，如图4-4d 所示。前面显示了NF A的一个优点是比接受同样的语言的DFA 需要少得多的状态数和更简洁的转移函数表，现在进一步放松条件后，新的NFA 可能需要更少的状态数和转移箭头。
问题：状态q0能否和状态q1合并？
定义4.4 带空转移的NFA （记为NFA-Λ）是一个5元组M=（Q, ∑, q0, δ, A），其中Q 和∑是非空有限集，q 0∈Q ，A ⊆Q ，转移函数定义为：
δ: Qx(∑⋃{Λ})→2Q
类似NFA 的定义（参见定义4.1），我们需要扩展定义连续转移函数δ，以便适用于NFA-Λ，它的基本思想是一致的，即δ*(q, x)表示的是字符串在NFA-Λ中从状态q 出发合法流动，最终停止在的状态。现在需要扩充定义的概念是“字符串在NFA-Λ中的合法流动”，或称为“NFA-Λ合法地处理字符串”。图4-5所示的简单例子可以说明这个概念。我们在字符串01中插入空字符Λ，得到0ΛΛ1Λ=x，显然x 能够被图4-5所示NFA-Λ接受。
2
问题：在一个长度为n 的字符串中插入Λ，可能的结果是C n ，实际使用中将带来组合爆炸，
不是可行的方法。
类似定义4.2a ，我们给出定义4.5a 。
定义4.5a （NFA-Λ的连续转移函数δ*的非递归定义）任给一个NFA-Λ M=（Q, ∑, q0, δ, A），p 和q 是属于Q 的任意两个状态，任给一个∑上的字符串x=a1a2...an，如果存在一个整数m>=n，序列b1, b2, ..., bm ∈∑⋃{Λ}满足b1b2...bm=x，存在一组状态p=p0, p1, ..., pm=q，对于每个1
函数δ*(p, x)的值是所有在x 驱动下，从状态p 转移到的所有状态组成的集合。
例如图4-5中，字符串01可以驱动状态从q0转移到f ，字符串Λ可以驱动状态从r 到t ，或每个状态到自身。类似定义4.2b ，我们给出递归定义，仍然利用字符串前缀计算的结果来定义整个字符串计算的结果，值得注意的是，我们还需要扩充递归基础的定义。显然δ*(q, Λ) 的结果不仅包含q ，还应该包含从q 出发经过Λ转移到达的其他状态。这里引入一个新的概念，空闭包（Λ-closure ，空转移闭包），表示从某个状态（或状态集）出发经过一次或多次空转移到达的所有状态组成的集合。
定义4.6 状态集的空闭包（Λ-closure of a set of states），给定NFA-Λ M=（Q, ∑, q0, δ, A），S 是Q 的子集，空闭包Λ(S)递归定义如下：
1. S 中每个元素都是Λ(S)的元素；
2. 如果q 是Λ(S)的元素，则δ(q, Λ) 中的每个元素都是Λ(S)的元素； 3. Λ(S)的元素只可能通过上面两步得到。
与大多数集合的递归定义不同的是，我们能够预先确定空闭包是一个有限集，因此可以将上面的递归定义转换成一个计算空闭包的算法（参见练习2.50）。规则1提供了初始值，规则2则提供了添加元素的方法，当Λ(S)不再增加时，则算法停止。
算法（计算Λ(S)），输入状态集S ，输出S 的空闭包，设为T 。 1. T=S
2. 循环，直到T 没有增加新元素
a) 循环，逐个检查T 中的元素q ，
T=T⋃δ(q, Λ) 。
定义4.5b （NFA-Λ的连续转移函数δ*的递归定义）给定一个NFA-Λ M=（Q, ∑, q0, δ, A），连续转移函数δ*: Qx∑*→2Q 定义如下：
1. δ*(q, Λ) = Λ({q})
2. δ*(q, ya) = Λ(
p ∈δ*(q , y )
⋃δ(p , a ) )
问题：对于DFA 和NFA 都有δ*(q, a)= δ(q, a)，但对于NFA-Λ，此式不成立。
对照定义4.2b ，就是在NFA 的连续转移函数计算的结果上，在进行一次空闭包计算。在识
别字符串的过程中，每读入一个字符，每次状态转移都要计算一次空闭包。字符串x 被NFA-Λ M 接受的判定条件与NFA 一致，当且仅当δ*(q, x)⋂A ≠φ。所有被M 接受的字符串组成被M 接受的语言，记为L(M)。 例子4.6 考虑图4.6所示的NFA-Λ，我们显示如何计算空闭包和连续转移函数。 分析： Λ({s}) = Λ({s, w})
= Λ({s, w, q0}) = Λ({s, w, q0, p, t}) = Λ({s, w, q0, p, t}) ---没有新元素加入，计算结束
现在计算δ*(q0, 010)，根据递归定义，需要计算δ*(q0, 01)、δ*(q0, 0)、δ*(q0, Λ) ，这里我们从底向上计算这组函数。
δ*(q0, Λ) = = δ*(q0, 0) =
= = = =
Λ({q0}) {q0, p, t} Λ(
p ∈δ*(q 0, Λ)
⋃δ(p , 0) )
Λ(δ(q0, 0)⋃δ(p, 0)⋃δ(t, 0)) Λ(φ⋃{p}⋃{u}) Λ({p, u}) {p, u} Λ(
p ∈δ*(q 0, 0)
δ*(q0, 01)=
= = =
⋃δ(p , 1) )
Λ(δ(p, 1)⋃δ(u, 1)) Λ({r}) {r} Λ(
p ∈δ*(q 0, 01)
δ*(q0, 010) =
⋃δ(p , 0) )
= Λ(δ(r, 0)) = Λ({s}) = {s, w, q0, p, t} 可见由于，δ*(q0, 010) 的结果含有w ，w 也是A 的元素，因此字符串010被图4-6所示的NFA-Λ接受。另外，010的同等字符串是Λ010Λ，容易发现存在状态序列q0, p, p, r, s, w接受字符串Λ010Λ。 显然连续转移函数的定义提供了一种高效的算法来判定字符串是否被NFA-Λ接受，如果采用插入空字符，然后借用NFA 的连续转移函数的计算方法，其时间复杂度为指数级。上述方法实际上是一种dynamic programming，Viterbi 算法。 问题1：写出计算NFA-Λ的连续转移函数的算法。 问题2：上述方法判定字符串是否被NFA-Λ接受，它能否回答判定中隐含插入的空字符位置？或判定中哪一步用到了空转移？比如能否知道010，在第一步和最后步用到了空转移？ 问题3：NFA-Λ可用于模糊查询，或两个字符串的模糊匹配，探寻如何在短的字符串中插入空字符，使得与长字符串达到最大匹配？
在4.1节我们说明了NFA 接受语言的能力与DFA 相当，现在我们要说明NFA-Λ接受语言的能力与NFA 相当，即每个NFA-Λ能够找到一个接受能力相当的NFA 。
定理4.2 对于任何一个NFA-Λ M=接受的语言L ，都存在一个NFA M 接受。（与定理4.1对比）
证明：设NFA-Λ M={Q, ∑, q0, A, δ}，要构造NFA M1={Q1, ∑, q1, A1, δ1}。
在定理4.1（为NFA 构造相当的DFA ）的证明中，我们通过重新定义状态集，从而消除了非确定性。NFA-Λ中的空转移也是一种非确定性，例如如果一个NFA-Λ中存在：
δ(p, 0)=q δ(q, Λ)=r
则状态p 在输入字符0时，有两个转移状态q 和r 。因此可以用类似δ(p, 0)=r的式子代替δ(q, Λ)=r，达到消除Λ的目的。显然凡是Λ(q)中的状态都可类似处理，即通过给空闭包中的每个状态添加转移箭头，就可以删除空转移。我们需要做的工作仅仅是消除一种特殊的非确定性情况。通用的方法如下。
Q1=Q q1=q0
我们利用空闭包实现NFA 的转移函数的构造。对于每个字符a ，至多插入两个空字符（非连续的空字符，因为连续的空字符相当于一个空字符），写成Λa Λ，因此在NFA-Λ中可能一个字符的转移至多两次涉及空闭包。
δ1(q, a) = Λ(
p ∈Λ({q })
⋃δ(p , a ) )
由于
δ*(q, a) = δ*(q, Λa)
= Λ(= Λ(
p ∈δ*(q , Λ)
⋃δ(p , a ) )
p ∈Λ({q })
⋃δ(p , a ) )
因此可以简写成 δ1(q, a) = δ*(q, a)
⎧A ⋃{q 0}A 1=⎨
⎩A
如果Λ({q 0})⋂A ≠φ否则
我们这样定义的目的是：对任意的状态q 和字符串x ，δ1*(q, x)= δ*(q, x)都成立。我们发现一个特例，当x=Λ时，除非我们重新构造Q1，否则无论怎么构造δ1，都难以保证上式成立。所幸的是，对任意非空字符串x ，上式成立。因此仅仅对A 稍作修改，构造的A 1，就能保证正确识别空串这个特例。
现在对字符串x 实施结构归纳法来证明δ1*(q, x)= δ*(q, x)成立。 1. 归纳基础，x=a单个字符
δ1*(q, a) = δ1(q, a) [δ1*是NFA 的转移函数]= δ*(q, a) 2. 归纳推理，设δ1*(q, y)= δ*(q, y)，
δ1*(q, ya) =
= =
p ∈δ1*(q , y )
⋃
δ1(p , a )
p ∈δ*(q , y )
⋃
δ1(p , a )
p ∈δ(q , y )
⋃*
δ*(p , a )
δ(p , a ) ) ，因此需要证明
p ∈δ*(q , y )
而δ*(q, ya) = Λ(
p ∈δ*(q , y )
⋃
p ∈δ(q , y )
⋃*⋃*
δ*(p , a ) = Λ(δ*(p , a ) =
⋃δ(p , a ) )
p ∈δ(q , y ) p ∈δ
⋃*
Λ⎛ ⋃δ(r , a ) ⎫⎪
(q , y ) ⎝r ∈Λ({p })⎭
---空闭包可移到外面
= Λ
⎛⋃⎛⋃δ(r , a ) ⎫⎫
⎪⎪
⎭⎭⎝p ∈δ*(q , y ) ⎝r ∈Λ({p })
⎛⋃⎛⋃δ(r , a ) ⎫⎫
⎪⎪*r ∈{p }p ∈δ(q , y ) ⎝⎭⎭⎝
= Λ
---δ*(q, y)已经计算了空闭包， 因此可去掉一层空闭包。
= Λ
⎛⋃δ(p , a ) ⎫
⎪
⎝p ∈δ*(q , y ) ⎭
现在我们证明构造NFA M1接受NFA-Λ M相同的语言，分两种情况讨论：
1. M 中Λ({q0})⋂A ≠φ，此时A1=A⋃{q0}，对判定的字符串x 分两种情况讨论
a) x=Λ
δ*(q0, Λ)=Λ({q0})，而Λ({q0})⋂A ≠φ，被M 接受
δ *(q0, Λ)=δ (q0, Λ)={q0}，而{q0}⋂A1={q0}≠φ，被M1接受 因此Λ同时被M 和M1接受。 b) x ≠Λ
δ *(q0, x)=δ*(q0, x)=B
要证明B ⋂A ≠φ当且仅当B ⋂A1≠φ。分两种情况： i. q0∈B ，则
Λ({q0})⊆B ，由于 Λ({q0})⋂A ≠φ，因此 B ⋂A ≠φ，x 被M 接受 另外，A1=A⋃{q0}，因此 B ⋂A1≠φ，x 被M1接受 x 被M 和M1同时接受。 ii. q0∉B ，则
B ⋂A= B⋂(A⋃{q0})= B⋂A1，因此
x 要么同时被M 和M1接受，要么同时被M 和M1拒绝。
2. M 中Λ({q0})⋂A=φ，此时A1=A，对判定的字符串x 分两种情况讨论
a) x=Λ
δ*(q0, Λ)=Λ({q0})，而Λ({q0})⋂A=φ，被M 拒绝；
δ *(q0, Λ)=δ (q0, Λ)={q0}，因为Λ({q0})⋂A=φ，则{q0}⋂A=φ，A1=A，因此 {q0}⋂A1=φ，被M1拒绝。
Λ同时被M 和M1拒绝。 b) x ≠Λ
δ *(q0, x)=δ*(q0, x)=B ，由于A1=A
因此B ⋂A ≠φ当且仅当B ⋂A1≠φ，即x 要么同时被M 和M1接受，要么同时被拒绝。
上面讨论证明，任意一个字符串x ，要么同时被M 和M1接受，要么同时被拒绝。因此M 和M1接受同样的语言。定理4.2证明完毕。
问题1：子集构造法能否类似定理4.1那样构造出相当的NFA ？ 问题2：直接从NFA-Λ构造DFA 的算法？
NFA 是DFA 的更通用的模型，NFA-Λ是NFA 的更通用模型，即我们可以说DFA 是NFA 的特殊情况，NFA 是NFA-Λ的特殊情况。
定理4.1和定理4.2的结论可以用下面的定理4.3来总结。
定理4.3 对于字母表∑上的任意语言L ，下面三个命题是相当的 1. L 可以被FA 接受（此处FA 就是DFA ） 2. L 可以被NFA 接受 3. L 可以被NFA-Λ接受
证明：根据定理4.1，2可以导出1；根据定理4.2，3可以导出2，现在只要证明1可以导出3。设L 是FA M=(Q, ∑, q0, A, δ) 接受的语言，构造接受L 的NFA-Λ M1=(Q, ∑, q0, A, δ1) 。仅仅需要重新定义转移函数，δ1: Q⨯(∑⋃{Λ})→2Q ，
δ1(q, Λ) = φ
δ1(q, a) = {δ(q, a)} 容易证明M1与M 接受相同的语言。 正如定理4.1，定理4.2的证明提供了一个消除NFA-Λ中空转移的算法，下面用两个例子来说明这个算法。这些例子也可用来作为消除非确定性的练习。
例子4.7 图4-7a 给出了一个NFA-Λ M，它接受的语言是0*(01)*0*，下面表显示了M 的转移函数和连续转移函数δ*(q, 0)和δ*(q, 1)的计算结果，这些结果可以用来构造相应的NFA M1。
M=({A, B, C, D}, {0, 1}, A, {D}, δ) 由于Λ({A})⋂{D}≠φ，因此，
M1=({A, B, C, D}, {0, 1}, A, {A, D}, δ1) ，δ1定义见上表。对图4-7a 删除空转移，添加新转移，得到图4-7b ，它表示的是相应的NFA 。可以进一步消除NFA 中的不确定性，得到相当的FA ，如图4-7c 所示。
例子4.8 图4-8a 给出了一个NFA-Λ M，它接受的语言是0*((01)*1+1*0)，下标显示了它的转移函数和相当NFA 的转移函数。
根据上表得到的NFA 如图4-8b 所示，注意初始状态A 不是接受状态，因为Λ({A})中没有接受状态。相当的FA 如图4-8c 所示。
4.3 Kleene 定理
本章的前两节提供了证明定理3.1的数学工具，定理3.1称为Kleene 定理，我们将其中的充分必要条件分成两部分来证明。
定理4.4 （Kleene 定理第一部分）任何一个正则语言都存在一个有限自动机接受。
证明：根据定理4.3，我们只需要证明存在一个带空转移的非确定型有限自动机（NFA-Λ）接受这个正则表达式表示的语言。由于正则语言存在一个递归定义，而要证明的是正则语言的一个性质，因此很适合使用结构归纳法。先构造接受三种最基本的正则语言的NFA-Λ，然后构造接受三种正则语言运算的NFA-Λ。
1. 归纳基础，根据定义3.1，三种最基本的正则语言分别是：φ、{Λ}和{a}，a 是字母表∑
上的任意一个字符。参见图4-9。
2. 归纳推理，证明在正则语言的三种运算下保持性质，分别为这三种运算构造有限自动
机。设接受语言L1和L2的NFA-Λ分别是： M1=(Q1, ∑, q1, A1, δ1) M2=(Q2, ∑, q2, A2, δ2)
不妨设Q1⋂Q2=φ（如果必要，可以更改状态名字），现在分别构造接受L 1⋃L 2、L 1L 2和L 1*的NFA-Λ Mu 、M c 和M k 。 M u =(Qu , ∑, qu , Au , δu ) ，其中
q u 是既不属于Q1，也不属于Q2的新状态； Q u =Q1⋃Q2⋃{qu }； A u =A1⋃A2
⎧{q 1, q 2}q =q u ∧a =Λ⎪φq =q u ∧a ≠Λ⎪
δu (q , a ) =⎨
q ∈Q 1
⎪δ1(q , a ) ⎪q ∈Q 2⎩δ2(q , a )
参见图4-10a ，增加了一个新状态，和从新状态到M1和M2的初始状态的空转移，完
成了一个分叉的构造。现在证明M u 接受的语言是L1⋃L 2。一方面，任给一个字符串x ∈L1⋃L 2，则x ∈L1或x ∈L2，不妨设x ∈L1，则M1接受x ，即存在M1的一组状态，p1=q1, p2, ..., pn∈A1，接受x ，由于从q u 到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=φ，因此p1, p2, ..., pn 都在M1中，且pn ∈A1，因此存在M1的一组状态p1, p2, ..., pn，接受x ，即x ∈L1⋃L 2。
Mc=(Qc , ∑, qc , Ac , δc ) ，其中 Q c =Q1⋃Q2； qc=q1; Ac=A2;
q ∈A 1∧a ≠Λ⎧δ1(q , a )
⎪δ(q , a ) ⋃{q }q ∈A ∧a =Λ⎪21
δc (q , a ) =⎨1
δ(q , a ) q ∈Q ∧q ∉A 111⎪⎪q ∈Q 2⎩δ2(q , a )
或
---此为书上式子
⎧δ1(q , Λ) ⋃{q 2}q ∈A 1∧a =Λ⎪
δc (q , a ) =⎨δ1(q , a ) q ∈Q 1
⎪δ(q , a ) q ∈Q 22⎩
---此为我的简化
参见图4-10b ，增加了从M1的接收状态到M2的初始状态的空转移。设M1接受的字
符串是x1，M2接受的字符串x2，则Mc 接受的字符串是x1Λx2=x1x2。
M k =(Qk , ∑, qk , Ak , δk ) ，其中 qk 是不属于Q1的新状态； Qk=Q1⋃{qk}； Ak={qk}；
{q 1}q =q k ∧a =Λ⎧⎪
δk (q , a ) =⎨δ1(q , Λ) ⋃{q k }q ∈A 1∧a =Λ
⎪δ(q , a ) (q ∈Q 1∧q ∉A 1) ∨(q ∈A 1∧a ≠Λ) 1⎩
参见图4-10c ，增加了一个新状态作为初始状态和唯一的接受状态，增加了从新状态到
原初始状态的空转移，从原接收状态到新状态的空转移，完成了一个环的构造。设被M1接受的一组字符串是x1, x2, ..., xm，则字符串(Λx1Λ)(Λx2Λ)...(Λxm Λ)=x1x2...xm能够被Mk 接受。
因此在3种运算下，保持了正则语言能够被NFA-Λ接受的性质。证明完毕。
问题1：构造方法与定理3.4的区别。
问题2：构造对应多个语言的合并和连接的自动机。
以上证明提供了从正则表达式构造NFA-Λ的方法，这种方法构造的自动机不一定是最简的。
例子4.9 构造正则表达式r=(00+1)*(10)*的NFA-Λ。
分析：构成r 的最基本的两个正则语言是{0}和{1}，它们对应的NFA-Λ如图4-11a 所示。然后构造{00}和{10}的NFA-Λ，如图4-11b 。图4-11c 显示了{00+1}的NFA-Λ，图4-11d 对应{00+1}*，图4-11e 对应(10)*，最终得到的NFA-Λ如图4-11f 所示。
严格按照定理4.4的算法构造的NFA-Λ往往有许多冗余的状态，图4-12给出了相应于图4-11的简化的NFA-Λ（参见练习4.35~4.37，简化NFA-Λ应该很小心）。尽管目前我们还没有简化NFA-Λ的形式化方法，但根据前两节的定理，我们知道如何将NFA-Λ转换成DFA ，第5章将讲述化简DFA 的形式化方法，因此最终存在一个简化自动机的方法。
定理4.5（Kleene 定理第二部分）任何一个有限自动机接受的语言都是正则语言。 证明：设L 是字母表∑上非空转移的确定型有限自动机DFA M=(Q, ∑, q0, A, δ) 接受的语言，即L={x∈∑* | δ*(q0, x)∈A}=⋃{x ∈∑*|δ*(q 0, x ) =q }。根据正则表达式定义，一组正则语言
q ∈A
的并集仍然是正则语言，我们只需要证明下面一组语言是正则语言： L(q0, q) = {x∈∑* | δ*(q0, x)=q∧q ∈A}，
更一般地，我们证明对M 的任意两个状态p 和q ，语言L(p, q) = {x∈∑* | δ*(p, x)=q }是正则语言。
很自然的证明方法是归纳法，比如根据L(p, q)中字符串的长度，或被接受的字符串从状态p 到q 所经过的状态数。这些方法也许不是很容易想到的有效方法，由于L(p, q)可以是无限集，则其中的字符串可以任意长，而且我们要证明的是整个语言的性质，而不是单个字符串的性质。因此根据经过的状态数是一种更好的归纳法。
现在我们假设M 共有n 个状态，并对每个状态编号，号码从1开始，到n 结束。我们给出概念“经过状态s 的路径”的形式化定义。给定一个字符串x ，如果存在两个非空的字符串y 和z ，满足：
x=yz，δ*(p, y)=s，δ*(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=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
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的证明提供了一个从有限自动机（确定型非空转移的有限自动机）导出相应正则表达式的方法，总结如下：
p ≠q ⎧{a ∈∑|δ(p , a ) =q }
L (p , q , 0) =⎨
{a ∈∑|δ(p , a ) =q }⋃{Λ}p =q ⎩
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=⋃L (q 0, q )
q ∈A
例子4.10 图4-14给出了一个FA ，求它对应的正则表达式。
分析：我们用下表显示对应语言L(p, q, j)的正则表达式r(p, q, j)，0=
上表在计算中，用到了一些简化方法，如：
r(1, 3, 1)=r(1, 3, 0) + r(1, 1, 0)r(1, 1, 0)*r(1, 3, 0)= φ
其中r(1, 3, 0)=φ，而空集与其他任何集合的连接运算结果仍是空集。 r(3, 2, 1) = r(3, 2, 0)+r(3, 1, 0)r(1,1,0)*r(1,2,0) = b+a(a+Λ)*b = Λb+a+b
= a*b
r(1,1,2) = r(1,1,1)+r(1,2,1)r(2,2,1)*r(2,1,1) = a* + a*b(a+b)*a+ = a* + a*(ba+)*ba+ = a* + a*(ba+) + = a*(ba+)* r(3,2,3) = r(3,2,1)+r(3,2,1)r(2,2,1)*r(2,2,1) = a*b + a*b(a+b)*(Λ+a+b) = a*b + a*b(a+b)*
= a*b(a+b)*
接受状态是1和2，因此要求的正则表达式r=r(1,1,3)+r(1,2,3)。 r(1,1,3) = r(1,1,2)+r(1,3,2)r(3,3,2)*r(3,1,2) = a*(ba+)*+a*(ba+)*bb(Λ+a*b(a+b)*b)*(a++a*(ba+) +) = a*(ba+)*+a*(ba+)*bb(a*(ba+)*bb)*(a++a*(ba+) +)
= a*(ba+)*+(a*(ba+)*bb)+(a++a*(ba+) +)
r(1,2,3) r
= r(1,2,2)+r(1,3,2)r(3,3,2)*r(3,2,2)
= a*(ba+)*b+a*(ba+)*bb(a*b(a+b)*b)*a*b(a+b)* = a*(ba+)*b+a*(ba+)*bb(a*(ba+)*bb)*a*b(a+b)* = a*(ba+)*b+(a*(ba+)*bb)+a*(ba+)*b = (a*(ba+)*bb)* a*(ba+)*b
= r(1,1,3)+r(1,2,3)
= a*(ba+)*+(a*(ba+)*bb)+(a++a*(ba+) +)+(a*(ba+)*bb)*a*(ba+)*b = a*(ba+)*+(a*(ba+)*bb)*(a*(ba+)*bb(a++a*(ba+) +)+a*(ba+)*b = a*(ba+)*+(a*(ba+)*bb)*a*(ba+)*(bba++bba*(ba+) ++b)
尽管希望能够进一步简化，但没有一个好的形式化方法。
问题：状态与字符串的关系。给定一个FA ，字符串与状态序列（或称路径）是一一对应关系，容易找到从字符串导出状态的方法，从状态导出字符串的方法。如果是NFA 呢？如果是NFA- 呢？