形式语言与自动机有穷自动机.ppt

《形式语言与自动机有穷自动机.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机有穷自动机.ppt（53页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、形式语言与自动机有穷自动机现在学习的是第1页，共53页第三章 有穷自动机o 1.1 非形式化描述o 1.2 有穷自动机的基本定义o 1.3 非确定的有穷自动机o 1.4 具有转移的有穷自动机o 1.5 有穷自动机的应用 o 1.6 具有输出的有穷自动机（*)现在学习的是第2页，共53页1.1 有穷状态系统o指针式钟表共有12*60*60个状态n 小时分钟秒o围棋共有3361个状态n 每一个格子：（空，黑，白）；n 格子数量：19行19列o某些电子产品中的开关电路，具有n个门的开关网络有2n种状态o“网上购物”系统（示例：）现在学习的是第3页，共53页o 2007年图灵奖年图灵奖 n模型检验（m

2、odel checking）:基于自动机理论的形式化方法(formal methods)E.ClarkEmersonSifakis现在学习的是第4页，共53页1.2 有穷自动机的基本定义定义3.1 一个有穷自动机有穷自动机(Finite Automata)简称简称FA，是一个五元组：M=(Q,q0,F)，其中（1）Q是有穷状态集；（States）（2）是有穷的输入字母表 （Alphabet）（3）是转移函数，它将QQ(全映射)；（Transiston function）（4）q0Q，是初始状态；（Initial state）（5）F Q，是终结状态集。（Accepting states）(终止

3、状态，接受状态)上述定义的另一个说法：确定型的有穷自动机确定型的有穷自动机(Deterministic Finite Automata：DFA)现在学习的是第5页，共53页DFA例子q0q1q21000,11字母表：S=0,1状态集：Q=q0,q1,q2初始状态：q0终结状态:F=q0,q1状态集输入01q0q1q2q0q1q2q2q2q1转换函数表 d:*问题：问题：1.接受什么特征的字符串？接受什么特征的字符串？2.状态状态q2起什么作用？起什么作用？现在学习的是第6页，共53页这两个DFA所接受的字符串集合分别是什么？DFA 例子q0q1baabS=a,bq0q1q2q3q4aaaaab

4、bbbbS=a,b现在学习的是第7页，共53页o设计一个DFA(字母表为0,1),接受如下字符串：o 设计一个DFA(字母表为0,1),接受如下特征的字符串：最多有三个1.q0q1011q20q31q4+0,1010DFA 例子L=010,1qeq0q1q01q010qdie0,10100,11010,1现在学习的是第8页，共53页o 设计一个DFA(字母表为0,1),接受所有结尾是01的字符串。o提示：DFA得记住 读入字符串的最后两位。DFA 例子qe01q0q1q00q10q01q1101010011100现在学习的是第9页，共53页o 设计一个DFA(字母表为0,1),接受所有结尾是1

5、01的字符串。DFA 例子现在学习的是第10页，共53页例3.1 给出一个有穷自动机=(q0,q1,q2,q3,0,1,q0,q0)其中：转移函数具体定义如下：(q0,1)=q1(q0,0)=q2 (q1,1)=q0(q1,0)=q3 (q2,1)=q3(q2,0)=q0 (q3,1)=q2(q3,0)=q1*DFA 例子现在学习的是第11页，共53页有穷自动机的扩充定义o定义3.2 对于有穷自动机M=(Q，q0，F)，它的扩充转移函数 ,是从Q*到Q的映射，其具体定义如下：（1）(q,)=q；（2）(q,wa)=(q,w),a)。其中qQ，w*，a。o例如，对于例3.1中的有穷自动机，就有：

6、(q0,010)=(q0,01),0)=(q0,0),1),0)=(q0,),0),1),0)=(q0,0),1),0)=(q2,1),0)=(q3,0)=q1。dddddddd现在学习的是第12页，共53页有穷自动机的基本定义o从到 的扩充是很自然的，就是 的特例（当|x|=1时）。o今后在提到FA的转移函数时，不再强调 这种写法，一律用表示，即的第二个变元既可以是单个字符也可以是一个字符串。ddd现在学习的是第13页，共53页有穷自动机模型o开始时，“读头”指向带上的第一个输入符号，控制器中放的是FA的初始状态。然后，依据转移函数做动作：若控制器中的当前状态是q，且“读头”指向带上符号为a

7、，则控制器中状态将变成p=(q,a)，且“读头”向右移指向带上下一个符号，如此可以继续进行下去。(注意：读头不能回头，只能一直向右移动)*现在学习的是第14页，共53页有穷自动机的模型o定义 3.3 给出FA：M=(Q,q0,F)，若(q0,x)=pF(x*)，则称字符串字符串x被被M接受接受。进一步地，被M接受的全部字符串构成的集合，称为被有穷自动机M接受的语言接受的语言，并记为L(M)。用集合描述法就是 L(M)=x (q0,x)F。oFA所能接受的只是*的一部分子集，有很多*的子集是任何FA都不能接受的。现在学习的是第15页，共53页从给定集合构造接受该集合的FAo例3.3：设计一个接受

8、能被5整除的二进制数的FA Mo用qs表示初始状态，用q0、q1、q2、q3、q4分别表示二进制数被5整除时余0（即能被5整除，所以它是终结状态。）、余1、余2、余3、余4的状态。现在学习的是第16页，共53页o一个FA(字母表为0,1),接受所有结尾是101的字符串。o能否给FA增加猜测选择的能力？假设我们具有猜测何时输入串还剩下三个字符的能力。1.3 非确定的有穷自动机(NFA)qdie101还剩三个字符010现在学习的是第17页，共53页NFAo每个状态对同样的一个输入字符，可能有0,1,或者多条转换发生（猜测）.1010,1q0q1q2q3现在学习的是第18页，共53页NFA：可以进行

9、猜测选择1010,1q0q1q2q3o 状态 q0 有两个标记为 1 的转换；o 读入1,NFA可以选择停留在q0，或者继续往前到状态q1现在学习的是第19页，共53页NFA：可以进行猜测选择1010,1q0q1q2q3o 状态q1 对于输入 1没有相应的转换；o q1 上读入1时,NFA就运行不下去了(die);而读入 0时候,NFA可以继续到状态q2；o 状态q2 类似的行为。现在学习的是第20页，共53页1010,1q0q1q2q3o q3 没有任何转换出来；o q3 上如果读入0,1,NFA也运行进入死状态。NFA：可以进行猜测选择现在学习的是第21页，共53页NFA：猜测的能力101

10、0,1q0q1q2q3猜测是否已经到了最后三位字符的位置了？如果是，则猜测最后三位字符应该是与101相匹配判断是否到达输入字符串的最末端NFA的运行过程中某个时刻是会的运行过程中某个时刻是会同时处于多个状态中同时处于多个状态中，只要输入串，只要输入串x结结束时束时NFA所处的多个状态中所处的多个状态中至少有一个是接受状态至少有一个是接受状态，就判断，就判断NFA接受接受x。现在学习的是第22页，共53页NFA的形式化定义o定义3.4 一个非确定的有穷自动机(Nondeterministic Finite Automata)简记为NFA，是一个五元组M=(Q,q0,F)其中Q、q0和F与确定的有

11、穷自动机的含意相同，只是转移函数的定义不同，它是从Q2Q（Q的幂集）上的映射。o在FA中，的一般形式是(q,a)=p(q,pQ)，而在NFA中，的一般形式是(q,a)=p1,p2,pk(piQ,i=1,2,k)，或(q,a)=（空集）。o在NFA中转移函数的取值是一个状态集，即使只有一个状态p，也要写成集合形式p。现在学习的是第23页，共53页NFA的形式化定义o定义3.5 对于NFA M=(Q,q0,F)，它的扩充转移函数 是从Q*2Q的映射，具体定义如下：(1)(q,)=q,(2)(q,wa)=p|p(r,a),r (q,w)。o对于例3.4中的NFA，(q0,01001)的求值过程如下图

12、：dddd现在学习的是第24页，共53页NFA接受的语言o定义3.7 给出NFA M=(Q,q0,F)，若(q0,x)F非空（x*），则称字符串x被M接受接受。被NFA M接受的全体字符串称为M接受的语言，记作L(M)。也就是 L(M)=xx*,且(q0,x)F非空非空。现在学习的是第25页，共53页NFA与 DFA的等价o NFA 能识别（接受）DFA所识别（接受）的所有语言。（为什么？）o 反过来成立吗？任一个NFA都能转换成一个DFA，二者所识别的语言是相等的。YES现在学习的是第26页，共53页NFA DFA:直观的理解100,1q0q1q2NFA:DFA:1q0q0 or q11q0

13、 or q21000现在学习的是第27页，共53页NFA DFA:子集构造法(subset construction)100,1q0q1q2NFA:DFA:q0,q1q0,q2q0,q1,q2q1,q2q0q1q2NFA中的任一个状态子集都是所构造的中的任一个状态子集都是所构造的DFA的一个状态的一个状态 现在学习的是第28页，共53页NFA DFA:状态之间的转换100,1q0q1q2NFA:DFA:q0,q1q0,q2q0,q1,q2q1,q2q0q1q201010,1010101010,1现在学习的是第29页，共53页NFA DFA:确定DFA接受状态100,1q0q1q2NFA:DFA

14、:q0,q1q0,q2q0,q1,q2q1,q2q0q1q201010,1010101010,1DFA中包含中包含NFA接受状态的子集状态设为接受状态的子集状态设为accepting现在学习的是第30页，共53页NFA DFA:消除无用的状态 100,1q0q1q2NFA:DFA:q0,q1q0,q2q0010101q0,q1,q2010q1,q2q1q201,1010,1将将DFA中不可达的状态消除掉。中不可达的状态消除掉。现在学习的是第31页，共53页子集构造法的一般步骤NFADFA状态q0,q1,qn,q0,q1,q0,q1,q0,qn每个状态都是每个状态都是NFA的一个子集的一个子集。

15、初始状态q0q0转换dd(qi1,qik,a)=d(qi1,a)d(qik,a)接受状态F Q F=S:S 包含 F中至少一个状态中至少一个状态 现在学习的是第32页，共53页NFA-DFA等价性的形式化证明o定理定理3.1 设设L是被一个非确定的有穷自动机接受的语言，是被一个非确定的有穷自动机接受的语言，则存在一个确定的有穷自动机也接受这个语言则存在一个确定的有穷自动机也接受这个语言L。证明 设 M=(Q,q0,F)是一个接受L的NFA，现在构造一个DFA M=(Q,q0,F)，其中：nQ=2Q,即Q的每一个子集作为Q的一个状态，若子集为q1,q2,qk，则 Q中状态记为q1,q2,qk；n

16、q0=q0；n F 2Q:F的每个元素至少包含F中的一个状态；n的定义为：(q1,q2,qi,a)=p1,p2,pj 当且仅当 （q1,q2,qi,a）=p1,p2,pj (a)。现在学习的是第33页，共53页NFA-DFA等价性的形式化证明o证明L(M)=L(M)=L。先证一个更一般的命题：(q0,x)=q1,q2,qk iff(q0,x)=q1,q2,qk（x*）。(3-1)对对x的长度的长度 x 用归纳来证明用归纳来证明。归纳基础归纳基础 x=0，即x=。因为(q0,)=q0=q0,(q0,)=q0。根据的定义。所以（3-1）式成立。归纳步骤归纳步骤 设对于|x|m的输入串（3-1）式成

17、立，现在考虑长度为m+1的输入串xa(x*，a)。因为一方面(q0,xa)=(q0,x),a)，（1）另一方面(q0,xa)=(q0,x),a)。（2）现在学习的是第34页，共53页NFA-DFA等价性的形式化证明o由归纳法假设，因为x长度为m，以下（3）式成立，即(q0,x)=p1,p2,pj当且仅当(q0,x)=p1,p2,pj。（3）再由的定义：(p1,p2,pj,a)=r1,r2,rs 当且仅当(p1,p2,pj,a)=r1,r2,rs （4）将（3），（4）代入（1），（2）两式，即得出(q0,xa)=r1,r2,rs 当且仅当(q0,xa)=r1,r2,rs。从而（3-1）式得到证

18、明。有了（3-1）式之后，若q1,q2,qkF,则q1,q2,qk 至少有一个在F中；反之，若q1,q2,qk中有一个状态在F中，则q1,q2,qkF。这就是说，M和M接受的语言是相同的，即L(M)=L(M)=L。定理证毕。o这个定理不仅证明了NFA和DFA两类自动机的等价性，而且还给出了从一给出了从一个个NFA构造与它等价的构造与它等价的DFA的具体步骤，这种证明称为构造性的证明方法。的具体步骤，这种证明称为构造性的证明方法。现在学习的是第35页，共53页NFA-DFA等价构造的例子o例3.5 设M=(q0,q1,0,1,q0,q1)是一个NFA，其中：（q0,0）=q0,q1,（q0,1）

19、=q1,（q1,0）=,（q1,1）=q0,q1。o根据定理3.1，我们能构造出等价的DFA:M=(Q,0,1,q0,F)其中：Q=q0,q1,q0,q1,F=q1,q0,q1,(q0,0)=q0,q1,(q0,1)=q1,(q1,0)=,(q1,1)=q0,q1,(q0,q1,0)=q0,q1,(q0,q1,1)=q0,q1,(,0)=,(,1)=。现在学习的是第36页，共53页子集构造法的实际实现o从状态q0出发，通过状态转移函数，逐步扩充状态集；每一步仅对状态集中新每一步仅对状态集中新增加的状态，才写出状态转移函数增加的状态，才写出状态转移函数；此过程一直继续下去，直到不再增加新，直到不

20、再增加新的状态为止的状态为止，最后就得到了DFA。o例 3.6 将例3.4中的NFA化为等价的DFA，可按下述步骤构造：第一步 从q0开始：(q0,0)=q0,q3,(q0,1)=q0,q1。第二步 处理两个新状态q0,q3和q0,q1：(q0,q3,0)=q0,q3,q4，(q0,q3,1)=q0,q1；(q0,q1,0)=q0,q3，(q0,q1,1)=q0,q1,q2。第三步 处理新增加的两个状态q0,q3,q4和q0,q1,q2：(q0,q3,q4,0)=q0,q3,q4,(q0,q3,q4,1)=q0,q1,q4；(q0,q1,q2,0)=q0,q3,q2,(q0,q1,q2,1)=

21、q0,q3,q2。现在学习的是第37页，共53页子集构造法的实际实现第四步第四步 处理新增加的两个状态处理新增加的两个状态q0,q1,q4和和q0,q3,q2：(q0,q1,q4,0)=q0,q3,q4,(q0,q1,q4,1)=q0,q1,q2,q4；(q0,q3,q2,0)=q0,q3,q4,q2,(q0,q3,q2,1)=q0,q1,q2。第五步第五步 处理新增加的两个状态处理新增加的两个状态q0,q1,q2,q4和和q0,q3,q4,q2：(q0,q1,q2,q4,0)=q0,q3,q4,q2,(q0,q1,q2,q4,1)=q0,q1,q2,q4；(q0,q3,q4,q2,0)=q0

22、,q3,q4,q2,(q0,q3,q4,q2,1)=q0,q1,q2,q4。o到这一步为止，不再增加新的状态，所求的DFA只包含9个状态。因为原来的NFA有5个状态，若按定理3.1的构造方法，就要设25=32个状态，是从初始状态q0不能到达的，不必把这些状态和相关的转移函数包含到所求的DFA中去。现在学习的是第38页，共53页1.4 具有转移的有穷自动机o该自动机的状态集为q0,q1,q2,输入字母表为0，1，2。o由初始状态q0开始，当接到输入符号0时，转移到状态q0本身，但不遇到任何符号（用表示）即可从q0转移到q1，从q1到q2也有类似的情况。o这种自动机在NFA的基础上又增加了一种不确

23、定性又增加了一种不确定性，它不仅在某些情况下有更简洁表达能力，而且在证明一些理论问题时，更是不可缺少的工具。现在学习的是第39页，共53页另一个-NFA的例子o设计一个NFA识别语言：字符串要么包含偶数个0，或奇数个1；r0r11100even number of 0ss0s10011odd number of 1sq0eee-transitions不需要读入任何符号即可发生状态转换现在学习的是第40页，共53页具有转移的有穷自动机o定义3.8 具有转移的有穷自动机（简称-NFA）是一个五元组M=(Q,q0,F)其中Q,q0,F的含义与一般的DFA或 NFA相同，而是从 Q()2Q的映射的映射

24、。o对于前面给出的自动机，它的函数是：(q0,0)=q0，(q0,)=q1，(q1,1)=q1，(q1,)=q2，(q2,2)=q2。o凡是没有写出的，如(q0,1)，(q1,2)，(q2,1)等等，都是没有定义的，这和一般的NFA相同。现在学习的是第41页，共53页具有转移的有穷自动机o定义3.9 在一个具有转移的有穷自动机中，对于状态q，它的-CLOSURE(q)是由下述规则定义的状态集：（1）q在-CLOSURE(q)中；（2）若p在-CLOSURE(q)中，则(p,)也都在-CLOSURE(q)中；（3）重复（2），直到-CLOSURE(q)中状态不再增加为止。进一步地，对于状态集P的

25、-CLOSURE，我们规定-CLOSURE(P)=-CLOSURE(q)。o所谓-CLOSURE(q)，从转移图上看，就是从状态从状态q出发，沿着标有出发，沿着标有的有向边所能达到的一切状的有向边所能达到的一切状态所构成的集合（包括状态态所构成的集合（包括状态q本身）本身）。所谓-CLOSURE(P)，就是对P中一切状态q，分别求出-CLOSURE(q)，然后将这些状态集求并而得的状态集。o例如，-CLOSURE(q0)=q0,q1,q2,-CLOSURE(q1)=q1,q2。Pq现在学习的是第42页，共53页具有转移的有穷自动机o定义3.10 对于一个具有转移的有穷自动机，它的扩充转移函数扩

26、充转移函数 定义如下：（1）(q,)=-CLOSURE(q),（2）(q,wa)=-CLOSURE(P),P=(r,a)。其中qQ,a,w*。o例3.6 考虑图3.11中的自动机 (q0,0)=-CLOSURE(q0,),0)=-CLOSURE(q0,q1,q2,0)=-CLOSURE(q0)=q0,q1,q2。(q0,01)=-CLOSURE(q0,0),1)=-CLOSURE(q0,q1,q2,1)=-CLOSURE(q1)=q1,q2。ddddddd)w,q(r d现在学习的是第43页，共53页具有转移的有穷自动机o定义3.11 对于一个具有转移的有穷自动机 M=(Q,q0,F)，它接受

27、的语言定义为：L(M)=w|d(q0,w)F非空非空。o定理定理3.2 如果如果L被一个具有被一个具有转移的有穷自动机接受，则转移的有穷自动机接受，则L也被一个不具有也被一个不具有转移的转移的NFA接受。接受。现在学习的是第44页，共53页具有转移的有穷自动机o证明(定理定理3.2)设M=(Q,q0,F)是具有转移的有穷自动机，且L(M)=L。现在构造M=(Q,q0 ,F)是一个不具有转移的NFA，其中：(q,a)=(q,a),qQ,a。如果-CLOSURE(q0)F非空，则F=Fq0；否则，F=F。下面我们将对x 作归纳法来证明下式：(q0,x)=(q0,x)。（3-2）注意当x=时，（3-

28、2）式不一定成立，因为(q0,)=q0，而 (q0,)=-CLOSURE(q0)。所以只能对 x 1证明(3-2)式成立。归纳基础 x=1，即x=a(a)。根据的定义，（3-2）式显然成立。dd现在学习的是第45页，共53页具有转移的有穷自动机o归纳步骤 设x=m(m1)时，（3-2）式成立，现在要证当 x=m+1时，（3-2）式成立。设x=wa (a,w=m)，则由的定义：(q0,wa)=(q0,w)，a)。（1）由归纳法假设，(q0,w)=(q0,w)。设 (q0,w)=P，则由的扩充定义：(P,a)=(q,a)=(q,a)。（2）另一方面，由 的定义：(q0,wa)=-CLOSURE(q

29、,a)。ddddddPqPqPq现在学习的是第46页，共53页具有转移的有穷自动机我们对（2）式的右部再进一步推导，得出 (q,a)=-CLOSURE(-CLOSURE（q）,a)=-CLOSURE(-CLOSURE（q）,a)=-CLOSURE(q,a)。（4）其中最后一步简化是因为对P=(q0,w)中的任何状态q,-CLOSURE(q)已经在P中，所以在对P中状态求和的情况下，可以将-CLOSURE(q)用q来代替。综合(1),(2),(3),(4)式，最后得出 (q0,wa)=(q0,wa)。到这里，我们用归纳法证明了对一切x(x 1)，（3-2）式成立。PqPqPqPqddd现在学习的

30、是第47页，共53页具有转移的有穷自动机o为了完成定理的证明，我们要证：对一切x*,(q,x)F非空，当且仅当 (q,x)F非空。o对x=和x分两种情况考虑。首先，当x=时，若M接受它，则-CLOSURE(q0)至少包含F中的一个状态，由F的定义，则q0在F中，那么M也接受。反之，若M接受，因为M是一个不具有转移的NFA，则q0必须在F中。进一步分析，若q0也在F中，则M自然接受；若q0不在F中，由F的定义，则-CLOSURE(q0)至少包含F中的一个状态，这也表示M接受。d现在学习的是第48页，共53页具有转移的有穷自动机o再考虑x的情况。设M接受x，即 (q0,x)包含F中的一个状态，则由

31、（3-2）式，(q0,x)也包含F中的同一个状态，而此状态自然也在F中，即M也接受x。反之，设M接受x，若(q0,x)包含F中的非q0状态（F中的一个状态），则由（3-2）式，(q0,x)也包含F中的这个状态，即M也接受x。但是，若(q0,x)包含q0，且q0不在F中，则根据F的定义，此时必有-CLOSURE(q0)F非空。再由（3-2）式，(q0,x)也包含q0，并进而包含-CLOSURE(q0)，因此，(q0,x)F非空，即M也接受x。定理证完。dddd现在学习的是第49页，共53页1.5 有穷自动机的应用o 在文本中查找字符串o用于文本搜索的非确定的有穷自动机o识别关键字集合的DFA现在

32、学习的是第50页，共53页在文本中查找字符串o在Web和其它在线文本库时代，一个常见的问题是，给定一个单词集合，查给定一个单词集合，查找包含一个（或全部）单词的所有文档找包含一个（或全部）单词的所有文档。搜索引擎是完成这个任务的一个专门的软件，它对Web上出现的每个单词（大约有一亿种不同的英文单词），保存这个单词所有出现之处的列表。要用非常大的主存的计算机保持这些列表的最常见部分，以便随时可用，允许许多人在瞬间搜索这些文档。o虽然在搜索引擎中常用的倒排索引技术没有使用有穷自动机，但有许多有关的应用不适合使用倒排索引,但很适合于应用基于自动机的技术。现在学习的是第51页，共53页用于文本搜索的非

33、确定的有穷自动机o例 3.9 假设要设计一个识别单词假设要设计一个识别单词web和和ebay出现的出现的NFA,用上述办法设计出的NFA如图3.14所示。其中状态1是初始状态，用符号表示中所有的字符。状态2到状态4完成识别web的任务，状态5到状态8完成识别ebay的任务。现在学习的是第52页，共53页用于文本搜索的非确定的有穷自动机o当然这个NFA还不是程序，对于这个NFA的实现，主要有两种方法：o写一个程序来模拟这个NFA，计算出读入每个输入字符后所处的状态的集合，检查什么时候达到终结状态（参见图3.10）。o用子集构造法将这个NFA化为等价的DFA。然后用程序直接模拟这个DFA。某些文本处理程序实际上混合采用这两种方法，但我们倾向于第（2）种方法。因为在这种特殊情况下从NFA转换为DFA是容易的，而且保证不增加状态数。现在学习的是第53页，共53页