第1章计算理论

第一部分

自动机与语言第1章正则语言研究内容有穷自动机非确定性正则表达式非正则语言1.1有穷自动机有穷自动机是描述能力和资源及其有限的计算机的模型自动机的直观概念成都重庆昆明贵阳207208189190火车车次表自动门控制器自动控制门的状态图两个状态：开和关四种可能的输入：FRONT;REAR;NEITHER;BOTH自动控制门接收信号：所经过的状态：自动控制门的状态转移表应用实例电子手表上4个键{a,b,c,d}有若干个状态，用自动机表示操作过程，比较简单（比现行说明书好用）电视机遥控电梯状态：电梯所在的楼层输入：从按钮接受到的信号电子恒温器录音机上的键和状态转换,，,计算器的控制器有穷自动机实质：现状＋输入

下一状态内存有限，只有寄存器，能记住状态（窍门：造自动机时遇到困难加状态，等于是加寄存器扩大了记忆力）一个典型的有穷自动机状态图状态：q1；q2；q3起始状态q1用一个指向它的无出发点的箭头表示；接受状态q2带有双圈转移：从一个状态指向另一个状态的箭头010:

拒绝11:

接受010100100100100:接受010000010010:拒绝:拒绝有穷自动机是描述能力和资源及其有限的计算机的模型如：自动控制器1.1.1有穷自动机的形式化定义有穷自动机（DFA：DeterministicFiniteAutomaton）M是一个5元组（5-tuple）M=(Q,,,q0,F)Q:是一个有穷集合，称为状态集

:有穷集合，称为字母表

:QQ是转换函数q0Q:是起始状态

FQ:接受状态集.转移函数定义动作规则，如：(x,1)=y表示当处于状态x时读到1，则转移到状态y1.1.1有穷自动机的形式化定义思考：是否允许没有接受状态？转移函数

对各个可能的输入符号从每一个状态是否一定恰好引出一个转移？有穷自动机形式化定义实例状态Q={q1,q2,q3}字母表={0,1}起始状态

q1接受状态

F={q2}转换函数

用矩阵描述为:q1q2q310010,1M=(Q,,,q,F)有穷状态自动机的状态转移图状态转移图(transitiondiagram)

⑴q∈Q

q是该有向图中的一个顶点；⑵

δ(q，a)=p

图中有一条从顶点q到顶点p的标记为a的弧；⑶

q∈F

标记为q的顶点被用双层圈标出；⑷

用标有S的箭头指出M的开始状态。状态转移图又可以叫做状态转换图。

1.1.1有穷自动机形式化定义若A是机器M接受的全部字符串集，则称A是机器M的语言，记L(M)=A。又称M接受A或M识别A一台机器可能接受若干字符串，但它永远只能识别一个语言1.1.2有穷自动机举例（1.2）图1-6为有穷自动机M2的状态图，从用形式化描述为：M2=({q1,q2},{0,1},,q1,{q2})，转移函数

为：221211qqqqqq10L(M2)={w|w以1结束}1.1.2有穷自动机举例（1.3）图1-7为有穷自动机M3的状态图L(M3)={w|w是空串或以0结束}1.1.2有穷自动机举例（1.4）图1-8为有穷自动机M4的状态图L(M4)={w|w是开头和结尾符号相同的字符串}1.1.2有穷自动机举例（1.5）图1-9为有穷自动机M5的状态图机器M5接受输入字符串中数字之和为3的倍数的字符串1.1.3计算的形式化定义正则语言如果一个语言被一台有穷自动机识别，则称它是正则语言1.1.4设计有穷自动机“读者即自动机”方法来设计1.1.4设计有穷自动机课堂练习（1）

构造一个DFA，它接受的语言为{x000y|x，y∈{0，1}*}q0——M的启动状态；q1——M读到了一个0，这个0可能是子串“000”的第1个0；q2——M在q1后紧接着又读到了一个0，这个0可能是子串“000”的第2个0；q3——M在q2后紧接着又读到了一个0，发现输入字符串含有子串“000”；因此，这个状态应该是终止状态。δ(q0,1)=q0——M在q0读到了一个1，它需要继续在q0“等待”可能是子串“000”的第1个0的输入字符0；δ(q1,1)=q0——M在刚刚读到了一个0后，读到了一个1，表明在读入这个1之前所读入的0并不是子串“000”的第1个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0；

δ(q2,1)=q0——M在刚刚发现了00后，读到了一个1，表明在读入这个1之前所读入的00并不是子串“000”的前两个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0；δ(q3,0)=q3——M找到了子串“000”，只用读入该串的剩余部分。δ(q3,1)=q3——M找到了子串“000”，只用读入该串的剩余部分。

M=({q0，q1，q2，q3}，{0，1}，{(q0,0)=q1，δ(q1,0)=q2，δ(q2,0)=q3，δ(q0,1)=q0，δ(q1,1)=q0，δ(q2,1)=q0，δ(q3,0)=q3，δ(q3,1)=q3}，q0，{q3})

状态说明状态输入字符01开始状态q0q1q0

q1q2q0

q2q3q0终止状态q3q3q3课堂练习（2）构造一个DFA，它接受的语言为{x000|x∈{0，1}*}。状态q0读到的0可能是输入字符串的最后三个0的第1个0；在状态q1紧接着读到的0可能是输入字符串的最后三个0的第2个0；在状态q2紧接着读到的0可能是输入字符串的最后三个0的第3个0；在状态q3紧接着读到的0也可能是输入字符串的最后三个0的第3个0；如果在状态q1，q2，q3读到的是1，则要重新检查输入串是否以三个0结尾。

课堂练习（3）构造一个DFA，它接受的语言为{x000|x∈{0，1}*}∪{x001|x∈{0，1}*}对于DFA来说，并行的弧按其上的标记字符的个数计算，对于每个顶点来说，它的出度恰好等于输入字母表中所含的字符的个数。不难看出，字符串x被FAM接受的充分必要条件是，在M的状态转移图中存在一条从开始状态到某一个终止状态的有向路，该有向路上从第1条边到最后一条边的标记依次并置而构成的字符串x。简称此路的标记为x。几点值得注意课堂练习（4）构造一个DFA，它接受的语言为{0n1m2k|n,m,k≥1}。

q0——M的启动状态；q1——M读到至少一个0，并等待读更多的0；q2——M读到至少一个0后，读到了至少一个1，并等待读更多的1；q3——M读到至少一个0后跟至少一个1后，并且接着读到了至少一个2。

有穷状态自动机⑴

当FA一旦进入状态qt，它就无法离开此状态。所以，qt相当于一个陷阱状态(trap)。一般地，我们将陷阱状态用作在其他状态下发现输入串不可能是该FA所识别的语言的句子时进入的状态。在此状态下，FA读完输入串中剩余的字符。

有穷状态自动机⑵

在构造一个识别给定语言的FA时，用画图的方式比较方便、直观。我们可以先根据语言的主要特征画出该FA的“主体框架”，然后再去考虑画出一些细节要求的内容。有穷状态自动机⑶

FA的状态具有一定的记忆功能：不同的状态对应于不同的情况，由于FA只有有穷个状态，所以，在识别一个语言的过程中，如果有无穷种情况需要记忆，我们肯定是无法构造出相应的FA的。

课堂练习（5）构造一个DFA，它接受的语言为{x|x∈{0，1}*，且当把x看成二进制数时，x模3与0同余}。

q0——对应除以3余数为0的x组成的等价类；q1——对应除以3余数为1的x组成的等价类；q2——对应除以3余数为2的x组成的等价类；qs——M的开始状态。qs——在此状态下读入0时，有x=0，所以应该进入状态q0；读入1时，有x=1，所以应该进入状态q1。即：δ(qs，0)=q0；δ(qs，1)=q1。q0——能引导M到达此状态的x除以3余0，所以有：x=3*n+0。读入0时，引导M到达下一个状态的字符串为x0，x0=2*(3*n+0)=3*2*n+0。所以，δ(q0，0)=q0；读入1时，M到达下一个状态的字符串为x1，x1=2*(3*n+0)+1=3*2*n+1。所以，δ(q0，1)=q1；q1——能引导M到达此状态的x除以3余1，所以有：x=3*n+1。读入0时，引导M到达下一个状态的字符串为x0，x0=2*(3*n+1)=3*2*n+2。所以即：δ(q1，0)=q2；读入1时，引导M到达下一个状态的字符串为x1，x1=2*(3*n+1)+1=3*2*n+2+1=3*(2*n+1)。所以δ(q1，1)=q0

q2——能引导M到达此状态的x除以3余2，所以：x=3*n+2。读入0时，引导M到达下一个状态的字符串为x0，x0=2*(3*n+2)=3*2*n+4=3*(2*n+1)+1。所以δ(q2，0)=q1；读入1时，引导M到达下一个状态的字符串为x1，x1=2*(3*n+2)+1=3*2*n+4+1=3*(2*n+1)+2。所以，δ(q2，1)=q2。1.1.5正则运算在计算理论中，对象是语言，工具包括为处理语言专门设计的运算。例并运算封闭：如果把某种运算应用于一个对象集合的成员得到的对象仍在这个集合中，则称这个对象集合在该运算下封闭定理1.12正则语言类在并运算下封闭证明思路：采用构造性证明，有两个正则语言A1和A2，要证明A1A2也是正则的。由于A1和A2是正则的，所以有一台有穷自动机M1识别A1和一台有穷自动机M2识别A2。为了证明A1A2是正则的，因而要证明有一台有穷自动机识别A1A2。连结运算定理1.13正则语言类在连结运算下封闭为证明链接定理遇到困难，

暂时放下，引入不确定性1.2非确定性Non-deterministic当机器处于给定的状态，并读入下一个输入符号时，可以知道机器的下一个状态是什么－它是确定的，称为确定型计算，而若在任何一点，下一个状态可能存在若干选择，称为非确定型计算非确定性有穷自动机NFA

NondeterministicAutomatonNFA:作为对DFA的修改

希望是接受{x|x∈{0，1}*，且x含有子串00或11}的FA如下：希望是接受{x|x∈{0，1}*，且x的倒数第10个字符为1}的FA如下：希望是接受所有含101或11作为子串的字符串的FA如下：这三个图所给的“FA”与前面我们所定义的DFA的区别在于：⑴

并不是对于所有的(q，a)∈∑×Q,δ(q，a)都有一个状态与它对应；⑵

并不是对于所有的(q，a)∈∑×Q,δ(q，a)只对应一个状态；(3)

转移箭头上的标号并不一定取自字母表中的符号；如：ε“FA”在任意时刻可以处于有穷多个状态。

“FA”具有“智能”。NFA的计算每读入一个符号后，机器把自己分裂成多个备份，并且并行地执行所有的可能性。对于机器的一个备份，如果下一个输入符号不出现在它所处的状态射出的任何箭头上，则机器的这个备份及其相关联的计算分支一块死掉。如果遇到一个状态，在射出的箭头上标有ε，不用读任何输入，机器分裂成多个备份，每一个标记ε的射出箭头上有一个备份跟踪，还有一个备份停留在当前状态。例思考：输入010字符串后，接受还是拒绝？构造接受{x|x∈{0，1}*，且x的倒数第3个字符为1}的NFA例把NFA转换成DFA在上图的NFA中，在从q2到q3和从q3到q4的箭头上的标号中添加ε后，它能识别什么样的语言？思考考虑下图的NFA，它的输入字母表{0}由一个符号组成。例：能接受所有形如0k的字符串，其中k是2或3的倍数1.2.1NFA的形式定义不确定的有穷状态自动机(non-deterministicfiniteautomaton,NFA)M是一个五元组M=(Q，∑，δ，q0，F)

Q:是一个有穷集合，称为状态集

:有穷集合，称为字母表

:Q

εP(Q)是转换函数q0Q:是起始状态

FQ:接受状态集.考虑下图的NFA，例：例接受{x|x∈{0，1}*，且x含有子串00或11}的FA对应的移动函数定义表。状态说明状态输入字符01启动状态q0{q0，q1}{q0，q2}

q1{q3}Φ

q2Φ{q3}终止状态q3{q3}{q3}接受{x|x∈{0，1}*，且x的倒数第10个字符为1}的FA对应的移动函数定义表。状态说明状态输入字符01启动状态q0{q0}{q0，q1}

q1{q2}{q2}

q2{q3}{q3}

q3{q4}{q4}

q4{q5}{q5}

q5{q6}{q6}

q6{q7}{q7}

q7{q8}{q8}

q8{q9}{q9}

q9{q10}{q10}终止状态q10ΦΦ思考：NFA比DFA能够识别更多的语言吗？1.2.2NFA与DFA的等价性

定理1.19：每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。（NFA与DFA等价）等价：如果两台机器能识别同样的语言，则称它们是等价的1.2.2NFA与DFA的等价性

NFA与DFA等价证明思路：设一个语言被一台NFA识别，那么必须证明还存在一台DFA也识别这个语言。NFA与DFA等价

对于一个输入字符，NFA与DFA的差异是前者可以进入若干个状态，而后者只能进入一个惟一的状态。虽然从DFA看待问题的角度来说，NFA在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的“总效果”相当于它处于这些状态对应的一个“综合状态”。因此，我们考虑让DFA用一个状态去对应NFA的一组状态。

证明：NFA与DFA等价

采用构造性证明证明：设N(Q，∑，δ，q0，F)是识别语言A的NFA，要构造一台DAFM识别A。假设N没有ε箭头构造一台识别语言A的DFAM=(Q’，∑，δ’，q0’，F’)（1）Q’＝P(Q)P(Q)是Q的所有子集组成的集合；（2）对于R∈Q’

和a∈∑，令δ’(R,a)={q∈Q|存在r∈R，使得q∈δ(r,a)}或表示为：

δ’(R,a)=证明：NFA与DFA等价

（3）q0’＝{q0}（4）F’={R∈Q’|R只包含N的一个接受状态}现在考虑N有ε箭头

E（R）={q|从R出发沿着0个或多个ε箭头可以到达q}

E（R）表示为从R出发只沿着ε箭头可以到达的状态集合，包括R本身的成员在内。

修改M的转移函数：

δ’(R,a)={q∈Q|存在r∈R，使得q∈E(δ(r,a))}修改M的起始状态：q0’＝E({q0})M的构造显然正确。在计算的每一步，M进入的状态明显地对应于N此时可能处于的状态子集，证毕。1.2.2NFA与DFA的等价性

推论1.20一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它1.2.2NFA与DFA的等价性DFA机器易算，NFA人易制造，通常，人造NFA,让机器把它变成DFA(yacc.exe)NFA的确定化关键技术:x的0步集E(x)起点E(1)={1,3},由起点，经a到达{1,3},经b到达{2}由{2}，经a到达{2,3},经b到达{3},…有23=8个状态（最大状态数），简化后6个注意{x,…}中要包含x的0步集E(x)231a,bbέaa例：给定NFAM1,造DFAM2使得识别结果一样例：把下图所示的NFA转换成对应的DFA。

表

状态转移函数状态说明状态输入字符01启动

[q0][q0,q1][q0,q2]

[q1][q3][Φ]

[q2][Φ][q3]终止

[q3][q3][q3]

[q0,q1][q0,q1,q3][q0,q2]

[q0,q2][q0,q1][q0,q2,q3]终止

[q0,q3][q0,q1,q3][q0,q2,q3]

[q1,q2][q3][q3]终止

[q1,q3][q3][q3]终止

[q2,q3][q3][q3]

[q0,q1,q2][q0,q1,q3][q0,q2,q3]终止

[q0,q1,q3][q0,q1,q3][q0,q2,q3]终止

[q0,q2,q3][q0,q1,q3][q0,q2,q3]终止

[q1,q2,q3][q3][q3]终止

[q0,q1,q2,q3][q0,q1,q3][q0,q2,q3]

[Φ][Φ][Φ]NFA与DFA等价

不可达状态(inaccessiblestate)：不存在从[q0]对应的顶点出发，到达该状态对应的顶点的路。我们称此状态从开始状态是不可达的。表中所有标记“

”的状态是从开始状态可达的，其他是不可达的——无用的。

构造给定NFA等价的DFA策略先只把开始状态[q0]填入表的状态列中，如果表中所列的状态列有未处理的，则任选一个未处理的状态[q1，q2，…，qn]，对∑中的每个字符a，计算δ([q1，q2，…，qn]，a)，并填入相应的表项中，如果δ([q1，q2，…，qn]，a)在表的状态列未出现过，则将它填入表的状态列。如此重复下去，直到表的状态列中不存在未处理的状态。

例

接受语言{0n1m2k|n，m，k≥0}的NFA

接受语言{0n1m2k|n，m，k≥0}的NFA是否可以构造成下图所示的“ε-NFA

”？其构造显然比上图所示的NFA更容易。状态转移表1.2.3在正则运算下的封闭性

定理1.22：正则语言类在并运算下封闭证明思路：采用构造性证明，有两个正则语言A1和A2，要证明A1A2也是正则的。想法是对A1和A2取两台NFAN1和N2，并把它们合并成一台新的NFAN1.2.3在正则运算下的封闭性

定理1.23：正则语言类在连接运算下封闭证明思路：采用构造性证明，有两个正则语言A1和A2，要证明A1

。A2也是正则的。想法是对A1和A2取两台NFAN1和N2，并把它们合并成一台新的NFAN1.2.3在正则运算下的封闭性

定理1.24：正则语言类在星号运算下封闭证明思路：有一个正则语言A1，要证明A1*也是正则的。想法是对A1取一台NFAN1，对它进行修改，使其识别A1*。只要能把输入分成若干段，并且N1接受每一段，则修改后的NFAN就接受这个输入。1.3正则表达式

RE

(RegularExpression)在算术中用运算符＋和×来构造表达式正则表达式：用正则运算符构造描述语言的表达式，如：在正则表达式中，连接苻常常省略优先级：星号运算－连结运算－并运算正则运算在计算理论中，对象是语言，工具包括为处理语言专门设计的运算。返回1.3正则表达式

RE

(RegularExpression)1.3.1RE的形式定义正则表达式(regularexpression，RE)⑴Φ是∑上的RE，它表示语言Φ；⑵ε是∑上的RE，它表示语言{ε}；⑶对于

a∈∑，a是∑上的RE，它表示语言{a}；⑷如果r和s分别是∑上表示语言R和S的RE，则：

r与s的“和”(r+s)是∑上的RE，(r+s)表达的语言为R∪S；r与s的“乘积”(rs)是∑上的RE，(rs)表达的语言为R。S；r的克林闭包(r*)是∑上的RE，(r*)表达的语言为R*。⑸只有满足⑴、⑵、⑶、⑷的才是∑上的RE。RR*记做R+。R+表示有一个或多个R中的串连结构成的所有串。将k个R中的串通过连结得到的串记做Rk例，其中“+”为并运算；例：设∑={0，1}⑴0，表示语言{0}；⑵1，表示语言{1}；⑶(0+1)，表示语言{0，1}；⑷(01)，表示语言{01}；⑸((0+1)*)，表示语言{0，1}*；⑹((00)((00)*))，表示语言{00}{00}*；⑺((((0+1)*)(0+1))((0+1)*))，表示语言{0，1}+；

⑻((((0+1)*)000)((0+1)*))，表示{0，1}上的至少含有3个连续0的串组成的语言；⑼((((0+1)*)0)1)，表示所有以01结尾的0、1字符串组成的语言；⑽(1(((0+1)*)0))，表示所有以1开头，并且以0结尾的0、1字符串组成的语言。

1.3.1RE的形式定义

约定

⑴r的正闭包r+表示r与(r*)的乘积（连结）以及(r*)与r的乘积：

r+=(r(r*))=((r*)r)⑵闭包（星号）运算的优先级最高，乘（连结）运算的优先级次之，加（并）运算“+”的优先级最低。所以，在意义明确时，可以省略其中某些括号。

((((0+1)*)000)((0+1)*))=(0+1)*000(0+1)*

RE的形式定义

((((0+1)*)(0+1))((0+1)*))=(0+1)*(0+1)(0+1)*

⑶在意义明确时，REr表示的语言记为L(r)，也可以直接地记为r。⑷

并、连结、星号运算均执行左结合规则。RE的形式定义相等(equivalence)r、s是字母表∑上的一个RE，如果L(r)=L(s)，则称r与s相等，记作r=s。相等也称为等价。几个基本结论⑴

结合律：(rs)t=r(st) (r+s)+t=r+(s+t)⑵

分配律：r(s+t)=rs+rt (s+t)r=sr+trRE的形式定义⑶

交换律：

r+s=s+r。⑷

幂等律：

r+r=r。⑸

加法运算零元素：r+Φ=r。⑹

乘法运算单位元：rε=εr=r。⑺

乘法运算零元素：rΦ=Φr=Φ。⑻L(Φ)=Φ。⑼L(ε)={ε}。⑽L(a)={a}。

RE的形式定义⑾

L(rs)=L(r)L(s)。⑿L(r+s)=L(r)∪L(s)。⒀L(r*)=(L(r))*。⒁L(Φ*)={ε}。⒂L((r+ε)*)=L(r*)。⒃L((r*)*)=L(r*)。⒄L((r*s*)*)=L((r+s)*)。⒅

如果L(r)

L(s)，则r+s=s。RE的形式定义⒆

L(rn)=(L(r))n。⒇rnrm=rn+m。一般地，

r+ε≠r，(rs)n

≠rnsn，rs≠sr。幂

r是字母表∑上的RE，r的n次幂定义为

⑴

r0=ε。⑵rn=rn-1r。

例设∑={0，1}00表示语言{00}；(0+1)*00(0+1)*表示所有的至少含两个连续0的0、1串组成的语言；(0+1)*1(0+1)9表示所有的倒数第10个字符为1的串组成的语言；L((0+1)*011)={x|x是以011结尾的0、1串}；L(0+1+2+)={0n1m2k|m，n，k≥1}；L(0*1*2*)={0n1m2k|m，n，k≥0}；L(1(0+1)*1+0(0+1)*0))={x|x的开头字符与尾字符相同}。注意1.3.2与有穷自动机的等价性定理1.28

一个语言是正则的，当且仅当可以用正则表达式描述它解释为：引理1.29如果一个语言可以用正则表达式描述，那么它是正则的。引理1.32：如果一个语言是正则的，则可以用正则表达式描述它。1.3.2与有穷自动机的等价性引理1.29：如果一个语言可以用正则表达式描述，那么它是正则的。证明思路：假设正则表达式R描述某语言A。要说明怎样把R转换成一台识别A的NFA（如果一台NFA识别A，则A是正则的）把R转换成一台NFAN，考虑正则表达式定义中的6种情况。证明：

R=εR=Φ

R=a

4）R=R1R2

4）R=R1R2，（或构造为：5）R=R1。R2

6）R=R1*6）R=R1*，（或构造为：RE到FA的等价变换1例：0对应的FA例：01对应的FARE到FA的等价变换2例：0+1对应的FARE到FA的等价变换3例：0*对应的FARE到FA的等价变换4例：分若干阶段把正则表达式(ab

a)*转换成一台NFA思考，能找出与上图等价的最小的NFA吗？RE到FA的等价变换5例：把正则表达式(a

b)*aba转换成一台NFARE到FA的等价变换6例：

构造与(0+1)*0+(00)*等价的FA。

按照对(0+1)*0+(00)*的“理解”

“直接地”构造出的FA。RE到FA的等价变换要点

按照定理证明给出的方法构造一个给定RE的等价FA时，该FA有可能含有许多的空移动。可以按照自己对给定RE的“理解”以及对FA的“理解”

“直接地”构造出一个比较“简单”的FA。定理证明中所给的方法是机械的。由于“直接地”构造出的FA的正确性依赖于构造者的“理解”，所以它的正确性缺乏有力的保证。

1.3.2与有穷自动机的等价性引理1.32：如果一个语言是正则的，则可以用正则表达式描述它。证明思路：如果语言A是正则的，则有一个正则表达式描述它。由于A是正则的，故它被一台DFA接受。（整个证明过程分为两部分，首先说明如何把DFA转换成GNFA－广义非确定型有穷自动机，然后说明如何把GNFA转换成正则表达式）广义非确定型有穷自动机GNFAGNFA实例GNFA的符合条件DFA转换成GNFA的过程GNFA转换成正则表达式的过程DFA转换成正则表达式的典型阶段典型等价变换示例1典型等价变换示例2定义把M转换成一台GNFA的过程CONVERT(G)DFA转换成正则表达式实例1DFA转换成正则表达式实例2DFA转换成正则表达式的图上作业法图上作业法操作步骤⑴预处理：①用标记为X和Y的状态将M“括起来”：在状态转移图中增加标记为X和Y的状态，从标记为X的状态到标记为q0的状态引一条标记为ε的弧；从标记为q(q∈F)的状态到标记为Y的状态分别引一条标记为ε的弧。②

去掉所有的不可达状态。DFA转换成正则表达式的图上作业法⑵

对通过步骤(1)处理所得到的状态转移图重复如下操作，直到该图中不再包含除了标记为X和Y外的其他状态，并且这两个状态之间最多只有一条弧。

并弧

将从q到p的标记为r1，r2，…，rg并行弧用从q到p的、标记为r1+r2+…+rg的弧取代这g个并行弧。

DFA转换成正则表达式的图上作业法去