形式语言与自动机理论电子教案-03省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件

第3章有穷状态自动机主要内容确定有穷状态自动机(DFA)作为对实际问题抽象、直观物理模型、形式定义，DFA接收句子、语言，状态转移图。不确定有穷状态自动机(NFA)定义；NFA与DFA等价性；1/1469/12/20231第3章有穷状态自动机带空移动有穷状态自动机(ε-NFA)定义。ε-NFA与DFA等价性。FA是正则语言识别器正则文法(RG)与FA等价性。相互转换方法。带输出有穷状态自动机。双向有穷状态自动机。2/1469/12/20232第3章有穷状态自动机重点：DFA概念，DFA、NFA、ε-NFA、RG之间等价转换思绪与方法。难点：对DFA概念了解，DFA、RG结构方法，RG与FA等价性证实。3/1469/12/202333.1语言识别

推导和归约中回溯问题将对系统效率产生极大影响

S

aA|aBA

aA|cB

aB|d分析句子aaac过程中可能需要回溯。4/1469/12/202343.1语言识别

系统识别语言{anc|n≥1}∪{and|n≥1}字符串过程中状态改变图示以下：

5/1469/12/202353.1语言识别识别系统(模型)⑴系统含有有穷个状态，不一样状态代表不一样意义。按照实际需要，系统能够在不一样状态下完成要求任务。⑵我们能够将输入字符串中出现字符聚集在一起组成一个字母表。系统处理全部字符串都是这个字母表上字符串。

6/1469/12/202363.1语言识别⑶系统在任何一个状态(当前状态)下，从输入字符串中读入一个字符，依据当前状态和读入这个字符转到新状态。当前状态和新状态能够是同一个状态，也能够是不一样状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一个字符后指向输入串下一个字符。

7/1469/12/202373.1语言识别⑷系统中有一个状态，它是系统开始状态，系统在这个状态下开始进行某个给定句子处理。

⑸系统中还有一些状态表示它到当前为止所读入字符组成字符串是语言一个句子，把全部将系统从开始状态引导到这种状态字符串放在一起组成一个语言，该语言就是系统所能识别语言。

8/1469/12/202383.1语言识别对应物理模型一个右端无穷输入带。一个有穷状态控制器(finitestatecontrol,FSC)。一个读头。

系统每一个动作由三个节拍组成：读入读头正注视字符；依据当前状态和读入字符改变有穷控制器状态；将读头向右移动一格。9/1469/12/202393.1语言识别

有穷状态自动机物理模型

10/1469/12/2023103.2有穷状态自动机有穷状态自动机(finiteautomaton,FA)

M=(Q，∑，δ，q0，F)Q——状态非空有穷集合。

q∈Q，q称为M一个状态(state)。∑——输入字母表(Inputalphabet)。输入字符串都是∑上字符串。

q0——q0∈Q，是M开始状态(initialstate)，也可叫做初始状态或者开启状态。11/1469/12/2023113.2有穷状态自动机δ——状态转移函数(transitionfunction)，有时候又叫做状态转换函数或者移动函数。δ：Q×∑

Q，对

(q，a)∈Q×∑，δ(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串下一个字符。F——F

Q，是M终止状态(finalstate)集合。

q∈F，q称为M终止状态，又称为接收状态(acceptstate)。

12/1469/12/2023123.2有穷状态自动机例3-1下面是一个有穷状态自动机

M1=({q0，q1，q2}，{0}，δ1，q0，{q2})其中，δ1(q0,0)=q1，δ1(q1,0)=q2，δ1(q2,0)=q1

用表3-1表示δ1。状态说明状态输入字符0开始状态q0q1

q1q2终止状态q2q113/1469/12/2023133.2有穷状态自动机M2=({q0，q1，q2，q3}，{0，1，2}，δ2，q0，{q2})δ2(q0,0)=q1，δ2(q1,0)=q2δ2(q2,0)=q1，δ2(q3,0)=q3δ2(q0,1)=q3，δ2(q1,1)=q3δ2(q2,1)=q3，δ2(q3,1)=q3δ2(q0,2)=q3，δ2(q1,2)=q3δ2(q2,2)=q3，δ2(q3,2)=q3

14/1469/12/2023143.2有穷状态自动机状态说明状态输入字符012开始状态q0q1q3q3

q1q2q3q3终止状态q2q1q3q3

q3q3q3q3表3-2

δ2转换函数

15/1469/12/2023153.2有穷状态自动机将δ扩充为对任意q∈Q，w∈∑*，a∈∑，定义

16/1469/12/2023163.2有穷状态自动机两值相同，不用区分这两个符号。

17/1469/12/2023173.2有穷状态自动机确定有穷状态自动机因为对于任意q∈Q，a∈∑，δ(q，a)都有确定值，所以，将这种FA称为确定有穷状态自动机(deterministicfiniteautomaton，DFA)

18/1469/12/2023183.2有穷状态自动机M接收(识别)语言

对于

x∈∑*假如δ(q，w)∈F，则称x被M接收，假如δ(q，w)

F，则称M不接收x。L(M)={x|x∈∑*且δ(q，w)∈F}称为由M接收(识别)语言

L(M1)=L(M2)={02n|n≥1}

假如L(M1)=L(M2)，则称M1与M2等价。

19/1469/12/2023193.2有穷状态自动机例3-2

结构一个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”；所以，这个状态应该是终止状态。20/1469/12/2023203.2有穷状态自动机δ(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；

21/1469/12/2023213.2有穷状态自动机δ(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”，只用读入该串剩下部分。

22/1469/12/2023223.2有穷状态自动机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终止状态q3q3q323/1469/12/2023233.2有穷状态自动机一个更为直观表示24/1469/12/2023243.2有穷状态自动机状态转移图(transitiondiagram)

⑴q∈Q

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

δ(q，a)=p

图中有一条从顶点q到顶点p标识为a弧；⑶q∈F

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

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

25/1469/12/2023253.2有穷状态自动机例3-3结构一个DFA，它接收语言为{x000|x∈{0，1}*}。状态q0读到0可能是输入字符串最终三个0第1个0；在状态q1紧接着读到0可能是输入字符串最终三个0第2个0；在状态q2紧接着读到0可能是输入字符串最终三个0第3个0；26/1469/12/2023263.2有穷状态自动机在状态q3紧接着读到0也可能是输入字符串最终三个0第3个0；假如在状态q1，q2，q3读到是1，则要重新检验输入串是否以三个0结尾。

27/1469/12/2023273.2有穷状态自动机几点值得注意⑴

定义FA时，经常只给出FA对应状态转移图就能够了。

⑵

对于DFA来说，并行弧按其上标识字符个数计算，对于每个顶点来说，它出度恰好等于输入字母表中所含字符个数。

28/1469/12/2023283.2有穷状态自动机⑶

不难看出，字符串x被FAM接收充分必要条件是，在M状态转移图中存在一条从开始状态到某一个终止状态有向路，该有向路上从第1条边到最终一条边标识依次并置而组成字符串x。简称此路标识为x。

⑷

一个FA能够有多于1个终止状态。

29/1469/12/2023293.2有穷状态自动机接收语言{x000|x∈{0，1}*}∪{x001|x∈{0，1}*}FA

30/1469/12/2023303.2有穷状态自动机即时描述(instantaneousdescription，ID）x，y∈∑*，δ(q0，x)=q,xqy称为M一个即时描述，表示xy是M正在处理一个字符串，x引导M从q0开启并抵达状态q，M当前正注视着y首字符。

假如xqay是M一个即时描述，且δ(q，a)=p，则xqay├Mxapy。

31/1469/12/2023313.2有穷状态自动机α├Mn

β：表示M从即时描述α经过n次移动抵达即时描述β。M存在即时描述α1，α2，……，αn-1，使得α├M

α1，α1├M

α2，…，αn-1├M

β当n=0时，有α=β。即α├M0α。α├M+

β：表示M从即时描述α经过最少1次移动抵达即时描述β。α├M*β：表示M从即时描述α经过若干步移动抵达即时描述β。

32/1469/12/2023323.2有穷状态自动机当意义清楚时，我们将符号├M、├Mn、├M*、├M+中M省去，分别用├、├n、├*、├+表示。

33/1469/12/2023333.2有穷状态自动机对下列图所表示DFA有以下ID转换：34/1469/12/2023343.2有穷状态自动机q01010010001├1q0010010001

├10q110010001

├101q00010001

├1010q1010001

├10100q210001

├101001q00001

├1010010q1001

├10100100q201

35/1469/12/2023353.2有穷状态自动机 ├101001000q31

├1010010001q0即q01010010001├10

1010010001q0q01010010001├+

1010010001q0q01010010001├*

1010010001q0

36/1469/12/2023363.2有穷状态自动机对于x∈∑*, q0x1├+

x1q0 q0x10├+

x10q1 q0x100├+x100q2 q0x000├+x000q3

37/1469/12/2023373.2有穷状态自动机能引导FA从开始状态抵达q字符串集合为： set(q)={x|x∈∑*，δ(q0，x)=q}对图3-3所给DFA中全部q，求set(q)。38/1469/12/202338set(q0)={x|x∈∑*，x=ε或者x以1结尾}set(q1)={x|x∈∑*，x=0或者x以10结尾}set(q2)={x|x∈∑*，x=00或者x以100结尾}set(q3)={x|x∈∑*，x以000结尾}set(q4)={x|x∈∑*，x以001结尾}这5个集合是两两互不相交。

39/1469/12/2023393.2有穷状态自动机对于任意一个FAM=(Q，∑，δ，q0，F)我们能够按照以下方式定义关系RM：对

x，y∈∑*，xRMy

q∈Q，使得x∈set(q)和y∈set(q)同时成立。按照这个定义所得到关系实际上是∑*上一个等价关系。利用这个关系，能够将∑*划分成不多于|Q|个等价类。

40/1469/12/2023403.2有穷状态自动机例3-4结构一个DFA，它接收语言为{0n1m2k|n,m,k≥1}。

q0——M开启状态；q1——M读到最少一个0，并等候读更多0；q2——M读到最少一个0后，读到了最少一个1，并等候读更多1；q3——M读到最少一个0后跟最少一个1后，而且接着读到了最少一个2。

41/1469/12/2023413.2有穷状态自动机先设计“主体框架”再补充细节42/1469/12/2023423.2有穷状态自动机⑴

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

43/1469/12/2023433.2有穷状态自动机⑵

在结构一个识别给定语言FA时，用画图方式比较方便、直观。我们能够先依据语言主要特征画出该FA“主体框架”，然后再去考虑画出一些细节要求内容。44/1469/12/2023443.2有穷状态自动机⑶FA状态含有一定记忆功效：不一样状态对应于不一样情况，因为FA只有有穷个状态，所以，在识别一个语言过程中，假如有没有穷种情况需要记忆，我们必定是无法结构出对应FA。

45/1469/12/2023453.2有穷状态自动机例3-5结构一个DFA，它接收语言为{x|x∈{0，1}*，且当把x看成二进制数时，x模3与0同余}。

q0——对应除以3余数为0x组成等价类；q1——对应除以3余数为1x组成等价类；q2——对应除以3余数为2x组成等价类；qs——M开始状态。46/1469/12/2023463.2有穷状态自动机qs——在此状态下读入0时，有x=0，所以应该进入状态q0；读入1时，有x=1，所以应该进入状态q1。即：δ(qs，0)=q0；δ(qs，1)=q1。47/1469/12/2023473.2有穷状态自动机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；48/1469/12/2023483.2有穷状态自动机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

49/1469/12/2023493.2有穷状态自动机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。50/1469/12/2023503.2有穷状态自动机接收语言{x|x∈{0，1}*，且当把x看成二进制数时，x模3与0同余}DFA以下：

51/1469/12/2023513.2有穷状态自动机例3-6

结构一个DFA，它接收语言L={x|x∈{0，1}*，且对x中任意一个长度小于5子串a1a2…an，a1+a2+…+an≤3，n≤5}。输入串为a1a2…ai…ai+4ai+5…am52/1469/12/2023523.2有穷状态自动机当i=1，2，3，也就是M读到输入串第1、2、3个字符时，它需要将这些字符记下来。因为a1……ai可能需要用来判定输入串最初4~5个字符组成子串是否满足语言要求。

当i=4，5，也就是M读到输入串第4、5个字符时，在a1+a2+……+ai≤3情况下，M需要将a1……ai记下来；在a1+a2+……+ai>3时，M应该进入陷阱状态qt。

53/1469/12/2023533.2有穷状态自动机当i=6，也就是M读到输入串第6个字符，此时，以前读到第1个字符a1就没有用了，此时它要看a2+a3+…+a6≤3是否成立，假如成立，M需要将a2…a6记下来；在a2+a3+…+ai>3时，M应该进入陷阱状态qt。

54/1469/12/2023543.2有穷状态自动机当M完成对子串a1a2…ai…ai+4考查，并发觉它满足语言要求时，M记下来是ai…ai+4，此时它读入输入串第i+5个字符ai+5，以前读到第i个字符ai就没有用了，此时它要看ai+1+ai+2+…+ai+5≤3是否成立，假如成立，M需要将ai+1，ai+2，…，ai+5记下来；在ai+1+ai+2+…+ai+5>3时，M应该进入陷阱状态qt。

55/1469/12/2023553.2有穷状态自动机M需要记忆内容有：什么都未读入——20=1种；统计有1个字符——21=2种；统计有2个字符——22=4种；统计有3个字符——23=8种；统计有4个字符——24-1=15种；统计有5个字符——25-6=26种；统计当前输入串不是句子——1种。

56/1469/12/2023563.2有穷状态自动机状态设置q[ε]——M还未读入任何字符；qt——陷阱状态；q[a1a2…ai]——M统计有i个字符，1≤i≤5。a1，a2，…，ai∈{0，1}。取DFAM=(Q，{0，1}，δ，q[ε]，F)F={q[ε]}∪{q[a1a2…ai]|a1，a2，…，ai∈{0，1}且1≤i≤5且a1+a2+…+ai≤3}Q={qt}∪F

57/1469/12/2023573.2有穷状态自动机δ(q[ε]，a1)=q[a1]δ(q[a1]，a2)=q[a1a2]δ(q[a1a2]，a3)=q[a1a2a3] q[a1a2a3a] 假如a1+a2+a3+a≤3δ(q[a1a2a3]，a)= qt

假如a1+a2+a3+a>3

58/1469/12/2023583.2有穷状态自动机 q[a1a2a3a4a]假如a1+a2+a3+a4+a≤3δ(q[a1a2a3a4]，a)= qt

假如a1+a2+a3+a4+a>3 q[a2a3a4a5a] a2+a3+a4+a5+a≤3δ(q[a1a2a3a4a5]，a)= qt

假如a2+a3+a4+a5+a>3δ(qt，a1)=qt59/1469/12/2023593.3NFA3.3.1作为对DFA修改

希望是接收{x|x∈{0，1}*，且x含有子串00或11}FA以下：60/1469/12/2023603.3.1作为对DFA修改希望是接收{x|x∈{0，1}*，且x倒数第10个字符为1}FA以下：61/1469/12/2023613.3.1作为对DFA修改这两个图所给“FA”与前面我们所定义FA，即DFA，区分在于：⑴

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

并不是对于全部(q，a)∈∑×Q,δ(q，a)只对应一个状态。

“FA”在任意时刻能够处于有穷多个状态。

“FA”含有“智能”。62/1469/12/2023623.3.2NFA形式定义不确定有穷状态自动机(non-deterministicfiniteautomaton,NFA)M是一个五元组M=(Q，∑，δ，q0，F)Q、∑、q0、F意义同DFA。δ：Q×∑

2Q，对

(q，a)∈Q×∑，δ(q，a)={p1，p2，…，pm}表示M在状态q读入字符a，能够选择地将状态变成p1、或者p2、…、或者pm，并将读头向右移动一个带方格而指向输入字符串下一个字符。

63/1469/12/2023633.3.2NFA形式定义FA状态转移图、FA状态对应等价类、FA即时描述对NFA都有效。接收{x|x∈{0，1}*，且x含有子串00或11}FA对应移动函数定义表。64/1469/12/2023643.3.2NFA形式定义状态说明状态输入字符01开启状态q0{q0，q1}{q0，q2}

q1{q3}Φ

q2Φ{q3}终止状态q3{q3}{q3}65/1469/12/2023653.3.2NFA形式定义接收{x|x∈{0，1}*，且x倒数第10个字符为1}FA对应移动函数定义表。66/1469/12/2023663.3.2NFA形式定义状态说明状态输入字符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ΦΦ67/1469/12/2023673.3.2NFA形式定义将δ扩充为对任意q∈Q，w∈∑*，a∈∑，定义

68/1469/12/2023683.3.2NFA形式定义和关于DFA结论一样，两值相同，也不用区分这两个符号。

69/1469/12/2023693.3.2NFA形式定义深入扩充δ定义域：δ：2Q×∑*

2Q。对任意P

Q，w∈∑*70/1469/12/2023703.3.2NFA形式定义因为，对

(q，w)∈Q×∑*

所以，不一定严格地域分δ第1个分量是一个状态还是一个含有一个元素集合。

71/1469/12/2023713.3.2NFA形式定义对任意q∈Q，w∈∑*，a∈∑：δ(q，wa)=δ(δ(q，w)，a)

对输入字符串a1a2…an

δ(q，a1a2…an)=δ((…δ(δ(q,a1),a2)，…)，an)。72/1469/12/2023723.3.2NFA形式定义M接收(识别)语言

对于

x∈∑*，假如δ(q0，w)∩F≠Φ，则称x被M接收，假如δ(q0，w)∩F=Φ，则称M不接收x。L(M)={x|x∈∑*且δ(q0，w)∩F≠Φ}，称为由M接收(识别)语言。

73/1469/12/2023733.3.3NFA与DFA等价

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

74/1469/12/2023743.3.3NFA与DFA等价

NFAM1=(Q，∑，δ1，q0，F1)与DFAM2=(Q2，∑，δ2，q0′，F2)对应关系：NFA从开始状态q0开启，我们就让对应DFA从状态[q0]开启。所以q0′=[q0]。

对于NFA一个状态组{q1，q2，…，qn}，假如NFA在此状态组时读入字符a后能够进入状态组{p1，p2，…，pm},则让对应DFA在状态[q1，q2，…，qn]读入字符a时，进入状态[p1，p2，…，pm]。

75/1469/12/2023753.3.3NFA与DFA等价

定理3-1NFA与DFA等价。证实：结构与M1等价DFAM2。

M1=(Q，∑，δ1，q0，F1)

M2=(Q2，∑，δ2，[q0]，F2)

Q2=2Q

F2={[p1，p2，…，pm]|{p1，p2，…，pm}

Q&{p1，p2，…，pm}∩F1≠Φ}

76/1469/12/2023763.3.3NFA与DFA等价

δ2([q1，q2，…，qn]，a)=[p1，p2，…，pm]

δ1({q1，q2，…，qn}，a)={p1，p2，…，pm}

(2)证实δ1(q0，x)={p1，p2，…，pm}

δ2([q0]，x)=[p1，p2，…，pm]。

设x∈∑*，施归纳于|x|

x=ε，δ1(q0，ε)={q0},δ2([q0]，ε)=[q0]

77/1469/12/2023773.3.3NFA与DFA等价

设当|x|=n是结论成立。下面证实当|x|=n+1是结论也成立。不妨设x=wa，|w|=n，a∈∑δ1(q0，wa)=δ1(δ1(q0，w)，a)=δ1({q1，q2，…，qn}，a)={p1，p2，…，pm}由归纳假设，δ1(q0，w)={q1，q2，…，qn}

δ2([q0]，w)=[q1，q2，…，qn]78/1469/12/2023783.3.3NFA与DFA等价

依据δ2定义，

δ2([q1，q2，…，qn]，a)=[p1，p2，…，pm]

δ1({q1，q2，…，qn}，a)={p1，p2，…，pm}

所以，

δ2([q0]，wa)=δ2(δ2([q0]，w)，a) =δ2([q1，q2，…，qn]，a) =[p1，p2，…，pm]

79/1469/12/2023793.3.3NFA与DFA等价

故，假如δ1(q0，wa)={p1，p2，…，pm}则必有δ2([q0]，wa)=[p1，p2，…，pm]。由上述推导可知，反向推导也成立。这就是说，结论对|x|=n+1也成立。由归纳法原理，结论对

x∈∑*成立。

80/1469/12/2023803.3.3NFA与DFA等价

(3)证实L(M1)=L(M2)

设x∈L(M1)，且δ1(q0，x)={p1，p2，…，pm}，从而δ1(q0，x)∩F1≠Φ,这就是说，{p1，p2，…，pm}∩F1≠Φ，由F2定义，[p1，p2，…，pm]∈F2。81/1469/12/2023813.3.3NFA与DFA等价再由(2)知，

δ2([q0]，x)=[p1，p2，…，pm]所以，x∈L(M2)。故L(M1)

L(M2)。反过来推，可得L(M2)

L(M1)。从而L(M1)=L(M2)得证。总而言之，定理成立。82/1469/12/202382例3-7

图3-9所表示NFA对应DFA状态转移函数如表3-7所表示。

图3-983/1469/12/202383表3-7状态转移函数状态说明状态输入字符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]

[Φ][Φ][Φ]84/1469/12/2023843.3.3NFA与DFA等价

不可达状态(inaccessiblestate)：不存在从[q0]对应顶点出发，抵达该状态对应顶点路。我们称此状态从开始状态是不可达。表3-7中，全部标识“

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

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

86/1469/12/2023863.3.3NFA与DFA等价图3-11图3-9所表示NFA等价DFA

87/1469/12/2023873.4带空移动有穷状态自动机

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

88/1469/12/2023883.4带空移动有穷状态自动机

接收语言{0n1m2k|n，m，k≥0}NFA是否能够结构成下列图所表示“ε-NFA

”？其结构显然比图1-13所表示NFA更轻易。当然还希望它们是等价。89/1469/12/2023893.4带空移动有穷状态自动机

带空移动不确定有穷状态自动机(non-deterministicfiniteautomatonwithε-moves,ε-NFA)M=(Q，∑，δ，q0，F)，Q、∑、q0、F意义同DFA。

δ：Q×(∑∪{ε})

2Q

90/1469/12/2023903.4带空移动有穷状态自动机

非空移动

(q，a)∈Q×∑δ(q，a)={p1，p2，…，pm}表示M在状态q读入字符a，能够选择地将状态变成p1、p2、…或者pm，并将读头向右移动一个带方格而指向输入字符串下一个字符。91/1469/12/2023913.4带空移动有穷状态自动机

空移动

q∈Qδ(q，ε)={p1，p2，…，pm}表示M在状态q不读入任何字符，能够选择地将状态变成p1、p2、…或者pm。也能够叫做M在状态q做一个空移动(又能够称为ε移动)，而且选择地将状态变成p1、p2、…或者pm。92/1469/12/2023923.4带空移动有穷状态自动机

深入扩充δ定义域：δ：2Q×∑*

2Q。对任意P

Q，w∈∑*。对任意q∈Q，w∈∑*，a∈∑。⑴

ε-CLOSURE(q)={p|从q到p有一条标识为ε路}。

93/1469/12/2023933.4带空移动有穷状态自动机94/1469/12/202394

3.4带空移动有穷状态自动机深入扩展移动函数：2Q×∑

2Q。

对任意(P，a)∈2Q×∑。

95/1469/12/2023953.4带空移动有穷状态自动机在ε-NFA中，对任意a∈∑，q∈Q，需要严格区分。96/1469/12/202396图3-14所表示ε-NFA状态δ

ε012ε012q0{q1}{q0}ΦΦ{q0,q1,q2}{q0,q1,q2}{q1,q2}{q2}q1{q2}Φ{q1}Φ{q1,q2}Φ{q1,q2}{q2}q2ΦΦΦ{q2}{q2}ΦΦ{q2}97/1469/12/2023973.4带空移动有穷状态自动机M接收(识别)语言

对于

x∈∑*，仅当

时，称x被M接收。

98/1469/12/2023983.4带空移动有穷状态自动机定理3-2ε-NFA与NFA等价。证实：设有ε-NFA

M1=(Q，∑，δ1，q0，F)(1)结构与之等价NFAM2。

取NFA

M2=(Q，∑，δ2，q0，F2)

F∪{q0} 假如F∩ε-CLOSURE(q0)≠ΦF2= F 假如F∩ε-CLOSURE(q0)=Φ

99/1469/12/2023993.4带空移动有穷状态自动机(2)施归纳于|x|，证实对

x∈∑+。δ2(q0，x)=δ2(q0，wa)=δ2(δ2(q0，w)，a)=δ2((q0，w)，a)

100/1469/12/20231003.4带空移动有穷状态自动机101/1469/12/20231013.4带空移动有穷状态自动机(3)证实,对

x∈∑+，δ2(q0，x)∩F2≠Φ充分必要条件是⑷

证实ε∈L(M1)

ε∈L(M2)

。102/1469/12/20231023.4带空移动有穷状态自动机例3-4求与图3-14所表示ε-NFA等价NFA。

103/1469/12/20231033.5FA是正则语言识别器

3.5.1FA与右线性文法

DFAM=(Q，∑，δ，q0，F)，处理句子a1a2…an特征。

⑴M按照句子a1a2…an中字符出现次序，从开始状态q0开始，依次处理字符a1、a2、…、an，在这个处理过程中，每处理一字符进入一个状态，最终停顿在某个终止状态。

104/1469/12/20231043.5.1FA与右线性文法⑵

它每次处理且仅处理一个字符：第i步处理输入字符ai。

⑶

对应于使用δ(q，a)=p状态转移函数处理，相当于是在状态q完成对a处理，然后由p接下去实现对后续字符处理。⑷

当δ(q，a)=p∈F，且a是输入串最终一个字符时，M完成对此输入串处理。

105/1469/12/20231053.5.1FA与右线性文法A0

a1A1

对应产生式A0

a1A1

a1a2A2

对应产生式A1

a2A2…

a1a2…an-1An-1 对应产生式An-2

an-1An-1

a1a2…an-1an

对应产生式An-1

an106/1469/12/20231063.5.1FA与右线性文法q0a1a2…an-1an├a1q1a2…an-1an 对应δ(q0，a1)=q1├a1a2q2…an-1an 对应δ(q1，a2)=q2

……├a1a2…an-1qn-1an 对应δ(qn-2，an-1)=qn-1├a1a2…an-1anqn 对应δ(qn-1，an)=qn

107/1469/12/20231073.5.1FA与右线性文法其中qn为M终止状态。考虑依据a1、a2、…、an，让A0与q0对应、A1与q1对应、A2与q2对应、…、An-2与qn-2对应、An-1与qn-1对应。这么，就有希望得到满足定理2-4-1正则文法推导与DFA相互模拟方式。

108/1469/12/20231083.5.1FA与右线性文法定理3-3FA接收语言是正则语言。证实：(1)结构。基本思想是让RG派生对应DFA移动。

设DFAM=(Q，∑，δ，q0，F)，取右线性文法G=(Q，∑，P，q0)，P={q

ap|δ(q，a)=p}∪{q

a|δ(q，a)=p∈F}109/1469/12/20231093.5.1FA与右线性文法（2）证实L(G)=L(M)-{ε}。对于a1a2…an-1an∈∑+，q0

+a1a2…an-1an

q0

a1q1，q1

a2q2，…， qn-2

an-1qn-1，qn-1

an∈P

δ(q0，a1)=q1，δ(q1，a2)=q2，…， δ(qn-2，an-1)=qn-1，δ(qn-1，an)=qn，且qn∈F

δ(q0，a1a2…an-1an)=qn∈F

a1a2…an-1an∈L(M)

110/1469/12/20231103.5.1FA与右线性文法（3）关于ε句子。

假如q0

F，则ε

L(M)，L(G)=L(M)。假如q0∈F，则由定理2-6和定理2-7，存在正则文法G′，使得L(G′)=L(G)∪{ε}=L(M)。总而言之，对于任意DFAM，存在正则文法G，使得L(G)=L(M)。定理得证。

111/1469/12/20231113.5.1FA与右线性文法例3-9与图3-8所给DFA等价正则文法qs

0|0q0|1q1q0

0|0q0|1q1q1

0q2|1|1q0q2

0q1|1q2112/1469/12/20231123.5.1FA与右线性文法与图3-7所给DFA等价正则文法

q0

0q1|1qt|2qt q1

0q1|1q2|2qt q2

0qt|1q2|2q3|2q3

0qt|1qt|2q3|2 qt

0qt|1qt|2qt

113/1469/12/20231133.5.1FA与右线性文法定理3-4正则语言能够由FA接收。

证实：（1）结构。基本思想：让FA模拟RG派生。设G=(V，T，P，S)，且ε

L(G)，取FAM=(V∪{Z}，T，δ，S，{Z})，Z

V。114/1469/12/20231143.5.1FA与右线性文法对

(a，A)∈T×V

{B|A

aB∈P}∪{Z} 假如A

a∈Pδ(A，a)= {B|A

aB∈P} 假如A

a

P用B∈δ(a，A)与产生式A

aB对应用Z∈δ(a，A)与产生式A

a对应。115/1469/12/20231153.5.1FA与右线性文法（2）证实L(M)=L(G)对于a1a2…an-1an∈T+， a1a2…an-1an∈L(G)

S

+a1a2…an-1an

S

a1A1

a1a2A2

…

a1a2…an-1An-1

a1a2…an-1an

S

a1A1，A1

a2A2，…， An-2

an-1An-1，An-1

an∈P116/1469/12/20231163.5.1FA与右线性文法A1∈δ(S，a1)，A2∈δ(A1，a2)，…， An-1∈δ(An-2，an-1)，Z∈δ(An-1，an)

Z∈δ(S，a1a2…an-1an)

a1a2…an-1an∈L(M)对于ε，按照定理2-5和定理2-6处理。117/1469/12/20231173.5.1FA与右线性文法例3-10

结构与所给正则文法等价FA：G1：E

0A|1B A

1|1C B

0|0C C

0B|1A

118/1469/12/20231183.5.1FA与右线性文法δ(E，0)={A} 对应E

0Aδ(E，1)={B} 对应E

1Bδ(A，1)={Z,C} 对应A

1|1Cδ(B，0)={Z,C} 对应B

0|0Cδ(C，0)={B} 对应C

0Bδ(C，1)={A} 对应C

1A119/1469/12/20231193.5.1FA与右线性文法120/1469/12/20231203.5.1FA与右线性文法推论3-1FA与正则文法等价。证实：依据定理3-3和定理3-4即可得到。

121/1469/12/20231213.5.1FA与左线性文法按照推导来说，句子a1a2…an-1an中字符被推导出先后次序恰好与它们在句子中出现次序相反；而按照归约来看，它们被归约成语法变量次序则恰好与它们在句子中出现次序相同：a1，a2，…，an-1，an。可见，归约过程与FA处理句子字符次序是一致，所以可考虑依照“归约”来研究FA结构。

122/1469/12/20231223.5.1FA与左线性文法对于形如A

a产生式：在推导中，一旦使用了这么产生式，句型就变成了句子，而且a是该句子第一个字符；按“归约”了解，对句子第1个字符，依据形如A

a产生式进行归约。对应到FA中，FA从开始状态出发，读到句子第一个字符a，应将它“归约”为A。我们假如考虑用语法变量对应FA状态，那么，此时我们需要引入一个开始状态，比如说：Z。这么，对应形如A

a产生式，能够定义A∈δ(Z，a)。

123/1469/12/20231233.5.1FA与左线性文法按照上面分析，对应于形如A

Ba产生式：FA应该在状态B读入a时，将状态转换到A。也能够了解为：在状态B，FA已经将当前句子、处理过前缀“归约”成了B，在此时它读入a时，要将Ba归约成A，所以，它进入状态A。

124/1469/12/20231243.5.1FA与左线性文法按照“归约”说法，假如一个句子是文法G产生语言正当句子，它最终应该被归约成文法G开始符号。所以，G开始符号对应状态就是对应FA终止状态。怎样处理好开始符号只有一个，而DFA终止状态能够有多个问题。

125/1469/12/20231253.5.1FA与左线性文法比如：对文法G2：E

A0|B1 A

1|C1 B

0|C0 C

B0|A1

对应δ(A，0)={E} δ(B，1)={E}δ(Z，1)={A}δ(C，1)={A}δ(Z，0)={B}δ(C，0)={B} δ(B，0)={C} δ(A，1)={C} 126/1469/12/20231263.5.1FA与左线性文法G2：E

A0|B1 A

1|C1 B

0|C0 C

B0|A1

127/1469/12/20231273.5.1FA与左线性文法DFA(状态转移图)作以下“预处理”：⑴

删除DFA陷阱状态(包含与之相关弧)；⑵

在图中加一个识别状态；⑶

“复制”一条原来抵达终止状态弧，使它从原来起点出发，抵达新添加识别状态。128/1469/12/20231283.5.1FA与左线性文法⑴

假如δ(A，a)=B，则有产生式B

Aa；⑵

假如δ(A，a)=B，且A是开始状态，则有产生式B

a。

定理3-5左线性文法与FA等价。

129/1469/12/20231293.6FA一些变形3.6.1双向有穷状态自动机

确定双向有穷状态自动机(two-waydeterministicfiniteautomaton，2DFA)M=(Q，∑，δ，q0，F)

Q、∑、q0、F意义同DFA。

130/1469/12/20231303.6.1双向有穷状态自动机δ：Q×∑

Q×{L，R，S}，对

(q，a)∈Q×∑

假如δ(q，a)={p，L}，它表示M在状态q读入字符a，将状态变成p，并将读头向左移动一个带方格而指向输入字符串前一个字符。

假如δ(q，a)={p，R}，它表示M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串中下一个字符。

假如δ(q，a)={p，S}，它表示M在状态q读入字符a，将状态变成p，读头保持在原位不动。

131/1469/12/20231313.6.1双向有穷状态自动机M接收语言

L(M)={x|q0x├*xp且p∈F}是2DFA接收语言。定理3-62DFA与FA等价。132/1469/12/20231323.6.1双向有穷状态自动机不确定双向有穷状态自动机(two-waynondeterministicfiniteautomaton，2NFA)M=(Q，∑，δ，q0，F)

Q、∑、q0、F意义同DFA。

δ：Q×∑

2Q×{L，R，S}

。