有限自动机理论3章有限状态自动机.ppt

第三章,有限状态自动机,定义语言,可以从两个方面进行： ）从产生语言的角度； ）从接收(或识别)语言的角度。,形式语言研究内容,产生一个语言: 1)定义语言中的基本句子; 2)根据其余句子的形成规则，产生出该语言所包含的所有句子。,有限自动机研究内容,使用某种自动机模型来接收字符串 接收的所有字符串形成的集合，也是一个语言,统一的理论,形式语言与自动机作为统一的理论,实际上包括3个方面的内容: 1) 形式语言理论(文法产生语言) 2) 自动机理论(自动机接收语言) 3) 形式语言与自动机的等价性理论 (文法与自动机等价转换),有限状态自动机 FA (Finite state Automaton),FA是为研究 有限存储的计算过程 正则语言 而抽象出的一种计算模型。,两类有限状态自动机,接收器 判断是否接收输入串； 转换器 对给定输入串产生输出。,FA还可以分为,确定的FA-DFA Deterministic Finite state Automaton 非确定FA- NFA Non-deterministic Finite state Automaton,等价性,有限状态自动机接收的语言称为有限状态语言-FSL 从产生语言角度而言， FSL就是右线性语言-RLL 从(正则)运算角度而言， FSL就是正则语言-RL,有限状态自动机除在理论上的研究价值外 还在数字电路设计、编译技术(词法分析)、系统辅助软件(文本编辑程序)、漏洞检测、交通控制等应用领域得到广泛应用,3.1 有限状态自动机,有限状态自动机是具有离散输入和离散输出的一种数学模型。 有限状态自动机是否接收串w 有限状态自动机是否接收语言L,有限状态自动机物理模型,a1,a2,a3,aj,an,an+1,FSC,一个输入存储带（输入带），带被分解为单元，每个单元存放一个输入符号(字母表上的符号)。 整个输入串从带的左端点开始存放，而带的右端可以无限扩充；,一个有穷状态控制器（FSC） 该控制器的状态只能是有限多个 FSC通过读头读取当前带上单元的字符。,初始时，读头对应带的最左单元，每读取一个字符，读头向右自动移动一个单元。 读头不允许向左移动。,有限状态自动机的一个动作为： 读头读取带上当前单元的字符 FSC根据当前FSC的状态和读取的字符，进行状态改变； 将读头向右移动一个单元。,有限态自动机的动作简化为： FSC根据 当前状态 和 当前读取的带上字符 进行状态改变。,定义3-1 有限状态自动机FA,FA是一个五元式 FA=(Q，q0，F) Q是有限状态的集合 是字母表，即输入带上的字符集合,q0Q是开始状态 FQ是接收状态(终止状态)集合,是QQ的状态转换函数 即(q，x)= q 代表自动机在状态q时，扫描字符x后到达状态q,有限状态自动机的状态转换函数的个数应该为 |Q|*| 对于Q中的每个状态，需要定义对应每个字母的状态转换。,DFA,这种有限状态自动机为确定的有限状态自动机DFA。,例3-1,定义DFA为： DFA=(q0,q1,0,1,q0,q0) 其中：,的表示：函数形式,(q0，0)=q1 (q0，1)=q1 (q1，0)= q1 (q1，1)= q0,的表示：状态矩阵,Q ,0,q0,1,q1,q1,q1,q1,q0,的表示:状态图形式,状态图是一个有向、有循环的图 一个节点表示一个状态； 若有(q，x)= q，则 状态q到状态q有一条有向边，并用字母x作标记。,的表示,指向的状态是开始状态 两个圆圈代表接收状态；,的表示：状态图,q1,1,0,1,0,q0,用状态图表示一个DFA 有向边的数目就是状态转换函数的个数。,默认,(q,)=q 不是状态转换函数,3.2 有限状态自动机接收语言,对于DFA，给定串w=x1x2xn 初始时， DFA处于开始状态q0 从左到右逐个字符地扫描串w,在(q0，x1)= q1的作用下 DFA处于状态q1 在(q1，x2)=q2的的作用下 DFA处于状态q2 ,当将串w扫描结束后， 若DFA处于某一个接收状态， 则有限状态自动机能够接收串w,对于可接收串,DFA从开始状态开始，在扫描串的过程中， 状态逐个地变化,串扫描结束后， 到达某个接收状态。,对于不可接收串,DFA从开始状态开始，在扫描串的过程中， 状态逐个地变化,串扫描结束后， 处于非接收状态。,对于字母表上的DFA 能够接收的所有串的集合，就是 DFA能接收的语言，记为L(DFA) 也称为有限状态语言（FSL）,思考,如何形式化定义L(DFA)?,定义3-4 扩展的状态转换函数,给定DFA，扩展的状态转换函数 *：Q*Q 即 *(q,w)=q 即DFA在一个状态q时，扫描串w后到达唯一确定的状态q,递归扩展的状态转换函数,*(q,)=q *(q,a)=(q,a) 其中a,对于串w=a（+） *（q， w） =*(q，a） =(*(q,),a),或者,对于串w= a *(q，w) =*(q，a) =*(q，a),),定义3-6 DFA接收的语言,DFA=(Q,q0，F)接收的语言 L(DFA)=w|*(q0,w)F,思考,如何描述 在某个时刻，DFA所处的情况？,定义3-7 DFA的瞬时描述（格局）,格局是一个二元式：qy q是DFA当前状态 y是输入带上还没有被扫描到的串 读头将扫描y串的第1个字母,在扫描串的过程中，格局在发生转换(改变) 格局的(一次)转换的原因是由于函数的(一次)作用,如果当前格局为：qar 有函数：(q，a)= q 则下一格局为： qr 格局的转换可以记为： qar = qr,DFA的特殊格局,初始格局为： q0w 接收格局为： qf 其中，qf是某个接收状态,使用=*代表格局的任意次转换 使用=+代表格局的多次转换,可以使用格局的转换方式定义FSL,DFA接收的语言 L(DFA)= w|q0w=*qf；w*且qfF,定义3-8 DFA停机,DFA将输入串扫描结束时 (自动)停机 这是DFA唯一的停机情况,注意1：,DFA将输入串扫描结束停机时， 如果DFA处于某一个接收状态， 则表示接收整个输入串； 反之，则表示不接收整个输入串;,注意2：,对于状态q,如果不能接收字母a 则将状态转换到一个特殊的状态：陷阱状态qt,陷阱状态qt不能够改变为其他状态 即 对于a (qt ，a)=qt qt不能够接收任意字母,构造DFA，分别接收语言,、0、01、 0*、 0+ (0+1)*、(0+1)+ 01*0 、1 *00(0+1) * (0+1) *00(0+1) * 0(0+1) *1 0(0+1) *0+1(0+1)*1 ,定理3-1,每个FSL都是一个右线性语言 分析： 已知 接收FSL的DFA 需要 构造RLG，使得 L(RLG)=FSL,等价思路,DFA最重要的部分是状态转换函数 文法最重要的部分是产生式 考虑状态转换函数和产生式的等价作用: 将状态转换函数改造为产生式,等价思路,状态转换函数和产生式的等价作用 (q, a)=q AaB 接收a 产生a 状态变化 非终结符号变化 结论:DFA状态等价于文法非终结符 状态转换函数等价于产生式,构造文法的基本思路：,将的DFA的状态当作是RLG的非终结符(开始状态就是开始符号) 对于某个句子： DFA通过状态的改变，逐步（自左向右）接收句子的每个字母； RLG通过非终结符号的改变，逐步（自左向右）产生句子的每个字母。,思考,DFA的接收状态的作用,证明,假设L是字母表上的FSL，则 L=L(DFA),DFA=（Q，q0，F） 构造右线性文法G=(,Q,q0，P） 其中P为：,qaq|(q，a)=q U qa|(q，a)F 特别，若q0是接收状态，则 q0,对于句子w=x1x2xn,DFA： 则文法有 (q0, x1)=q1 q0x1q1 (q1, x2)=q2 q1x2q2 (qn-2,xn-1)=qn-1 qn-2xn-1qn-1 (qn-1, xn)=qn qn-1xnqn 或 qn-1xn,所以,DFA 文法 *(q，)=q q=*q *(q0， w)F q0=*w 注意： 陷进状态在文法中是无用非终结符,例3-2 DFA与文法的转换,FSL=(0,1)1*0* 接收该语言的DFA为：,q1,1,0,0,1,q0,构造正则文法产生该语言： q00q1|1q1| q10q0|1q1| 0,定理3-2,FSL对补运算封闭,证明：,设L1是上的FSL,且L1=L(DFA1)， DFA1=（Q，q0，F）,构造 DFA2=（Q，q0，Q） DFA2接收的语言是 L1的对应的全集,即*,构造 DFA3=(Q，q0，Q-F) L3=L(DFA3) L3接收的语言是L1(关于*)的补 L3也是FSL语言。,注意,此时的DFA1的函数的个数为 |Q|*|,基本的等价替换,对于状态转换图，有基本的等价替换 变换为,0,1,1,3.3 DFA接收语言的例子,构造DFA，接收语言 L=ab,基本结构（接收基本句子）,q1,a,b,q0,q2,增加陷阱状态后的DFA,q1,a,b,q0,qt,b,a,a, b,a, b,q2,思考1,如果将该DFA的所有状态都设置为接收状态(包括陷阱状态)， 接收的语言是？,思考2,如果将该自动机的接收状态和非接收状态对调 接收的语言是？,例3-4构造DFA,接收语言L=x000y|x,y0,1*,分析,该语言的特点是 语言中的每个串都包含连续的3个0（即每个串都包含子串000）,因此，对于任何输入串，有限状态自动机的任务就是要检查该输入串中是否存在子串000， 一旦发现输入串包含有000，则表示整个输入串是句子。,因此，在确认输入串包含000后， 就可以逐一地读入000后面的全部字符，并接收该输入串。,思考,问题的关键是？ 如何发现子串000。,由于字符是逐一读入的，当从输入串中读入一个0时， 它有可能是000的第1个0， 需要记住已经出现过一个0；,如果紧接着读入的是字符1， 则刚读入的0就不是000的第1个0 需要重新寻找000子串的第1个0；,如果紧接着读入的还是0，它有可能是000的第2个0， 也需要记住这个0， 继续读入字符，若是0，则发现000 否则，需要重新寻找000。,初始状态：q0 接收0，到达状态q1 接收00 ,到达状态q2 接收000,到达状态q3,因此，基本的状态转移函数为： (q0，0)=q1 (q1，0)=q2 (q2，0)=q3 用于接收基本句子000,接收000的状态图,q0,0,0,0,q1,q2,q3,其他状态转移函数为： (q0，1)=q0 期待0的出现 (q1，1)=q0 重新寻找000 (q2，1)=q0 重新寻找000 (q3，0)=q3 扫描后续字符 (q3，1)=q3 扫描后续字符,状态转移图,q0,0,1,1,1,0,0,0,1,q1,q2,q3,思考,如果需要接收语言 L 如何修改有限状态自动机? 思路：考虑开始状态的作用,思考:如果,DFA的开始状态只负责接收输入串的第一个字母； 文法的开始符号只负责串的推导的开始； 优点是？,状态图为,例3-5构造DFA,接收语言 L=x001y|x，y0，1*,分析：,对于任何输入串，DFA的任务就是要检查该输入串中是否存在001,初始状态：q0 q1 已接收0 q2 已接收00 q3 已接收001,q2,q1,q0,状态转移图,0,1,q3,1,0,1,0,1,0,例3-6 构造DFA,接收语言L=x000|x0，1*,q2,q3,q1,q0,0,1,1,1,0,0,0,1,例3-7构造DFA,接收语言L=x000x001 其中，x0，1*,q2,q1,q0,0,1,q3,1,0,0,0,1,q4,1,0,1,例3-8构造DFA,接收语言L=02k+3m|m,k=0,实际上： 2k+3m 可以表示任意的非负整数(除1外) 该语言为0*-0,状态转移图,0,0,0,q1,q2,q0,思考：构造DFA,接收语言L=02k+3m|m,k0,例3-9构造DFA,接收0，1上的语言，该语言的 每个句子以0开头，以1结尾。,状态转移图,0,1,0,q1,q2,1,0,qt,0,1,1,q0,例3-10 构造DFA,接收0，1上的语言，该语言的每个字符串 不包含00子串(语言允许 ),0,0,0,1,qt,q1,q0,q2,1,0,1,1,或,0,0,0,1,qt,q1,q0,1,1,构造DFA,接收0，1上的语言， 该语言的每个字符串不包含00 （语言不允许 ）,例3-11构造DFA,接收0，1，2上的语言， 该语言的每个字符串代表的数字能整除3。,分析,如果一个十进制整数的所有位的数字的和能够整除3，那么， 这个十进制整数就能够整除3；,一个十进制整数除以3，余数只能是1、2和0；,将整数当作一个字符串，从左到右逐一地读入； 使用3个状态分别代表已读入的数字的和除以3的余数情况： (即读入的整数对3的余数情况）,q0：已读入的整数除以3，余数为0 q1：已读入的整数除以3，余数为1 q2：已读入的整数除以3，余数为2,思考,已知 qi(i =0,1,2)，k=0,1,2 应该如何确定 j？,qi,qj,k,扫描子串w后,处于某个状态qi， 读入当前数字, 状态转换情况为,q0,在此状态读入0，引导DFA到达下一状态的输入串为w0, w0的各位数字和除以3，余数为0。所以， DFA在q0状态读入0，应该继续保持q0状态；,q0,在此状态读入1，引导DFA到达下一状态的输入串为w1，w1的各位数字和除以3，余数为1。 所以， DFA在q0状态读入1，应该到达q1状态；,q0,在此状态读入2，引导DFA到达下一状态的输入串为w2，w2的各位数字和除以3，余数为2。 所以， DFA在q0状态读入2，应该到达q2状态； ,存在的问题,接收的串包括以0开始的数字串； 还能够接收空串,思考,如何进行改进，使得 接收的串不能以0开始， 不能接收空串。,定义3-9 set集合,对于状态q，能将DFA从q0转换到q状态的所有字符串的集合为： set(q)=w|w*,*(q0,w)=q,则有限状态自动机DFA接收的语言可以定义为： L(DFA)= set(q) 其中： qF,按状态进行划分,对于DFA，可以定义关系R 若 x,y* ，qQ 则 xRy 当且仅当 xset(q),yset(q) 即R=(x,y)|xset(q),yset(q) ；qQ 是*上的二元关系,该关系是集合*上的一个等价关系，利用该关系， 可以将*划分为不多于|Q|个的等价类。,DFA可以按照语言的特点给出字母表*的一个划分，这种划分相当于*上的一个等价分类。 DFA每个状态对应着一个等价类,利用一个状态去表示一个等价类是构造DFA的一条有效思路。,例3-12构造DFA,接收,0,1,2,4,5,6,7,8,9上的语言， 该语言的每个字符串代表的数字能整除3。,仍然只使用3个状态分别代表已经读入的整数字的和除以3的不同的余数的情况：,状态与对应的等价类,q0：余数为0的输入串的等价类 q1：余数为1的输入串的等价类 q2：余数为2的输入串的等价类,例3-13构造DFA,接收,0，1上的语言，该语言的每个字符串挡成二进制数时， 代表的数字能整除3。,DFA的每个状态对应一个等价类 利用一个状态去表示一个等价类 除以3的余数只能为0、1和2,q0：余数为0的输入串的等价类； q1：余数为1的输入串的等价类； q2：余数为2的输入串的等价类；,不能接收空串，所以， 还需要一个开始状态qS,人们习惯使用十进制数,w=x1x2x3xn (x1x2x3xn)2=(x1*2n-1+ x2*2n-2+ xn-1*2+xn)10 当串长度增加1时： (x1x2x3xnxn+1)2= (x1*2n+ x2*2n-1+ xn-1*22+ xn*2+xn+1)10 =(2*(w)10+xn+1)10,(w)10=3n+i (wx)10 =(2*(w)10+x)10 =6*n+2*i+x 实际上 2*i+x 对3的余数就是wx对3的余数,设w是当前已经读入的输入串； qS：开始状态 读入0时，进入状态q0 读入1时，进入状态q1,q0,能引导DFA到达此状态的w除以3余数为0，因此 (w)10=3n+0,q0,在此状态读入0，引导DFA到达下一状态的输入串为w0，则 (w0)10=2(3n+0)+0=32n+0 表明w0也属于q0对应的等价类。所以，DFA在q0状态读入0，应该继续保持q0状态；,q0,在此状态读入1，引导DFA到达下一状态的输入串为w1，则 (w1)10=2(3n+0)+1=32n+1 表明w1属于q1对应的等价类。所以， DFA在q0状态读入1，应该到达q1状态；,q1,能引导DFA到达此状态的w除以3余数为1，因此 (w)10=3n+1,q1,在此状态读入0，引导DFA到达下一状态的输入串为w0，则 (w0)10=2(3n+1)+0=32n+2 表明w0属于q2对应的等价类。所以， DFA在q1状态读入0，应该到达q2状态；,q1,在此状态读入1，引导DFA到达下一状态的输入串为w1，则 (w1)10=2(3n+1)+1=32n+3 表明w1属于q0对应的等价类。所以， DFA在q1状态读入1，应该到达q0状态；,q2,能引导DFA到达此状态的w除以3余数为2，因此， (w)10=3n+2,q2,在此状态读入0，引导DFA到达下一状态的输入串为w0，则 (w0)10=2(3n+2)+0=32n+4 表明w0属于q1对应的等价类。所以，DFA在q2状态读入0，应该到达q1状态；,q2,在此状态读入1，引导自动机到达下一状态的输入串为w1，则 (w1)10=2(3n+2)+1=32n+5 表明w1属于q2对应的等价类。所以，自动机在q2状态读入1，继续保持q2状态；,状态图,例3-14构造DFA，接收,0，1上的语言，该语言的每个字符串为二进制数时， 代表的数字能被5整除。,分析：,对5的余数只能为0、1、2、3和4 使用5个状态分别代表已经读入的数字除以5的不同的余数的等价类： qi：已经读入的数除以5，余数为i的输入串的等价类； 其中 i=0,1,2,3,4 不能接收空串，需要一个开始状态qS,例3-15构造DFA，接收,1,2,3上的语言，该语言的每个字符串挡成十进制数时， 代表的数字能被4整除。,思考：构造DFA，接收,0，1,2，3，4，5，6，7，8，9上的语言，该语言的每个字符串挡成十进制数时， 代表的数字能整除7 。 ,总结：构造DFA，接收,=x1, x2,x3,xm上的语言 该语言的每个字符串挡成base进制数时 代表的数字能整除N 或 代表的数字对N的余数为K,分析：,对N的余数只能为0、1、2、3、和N-1 使用N个状态分别代表已经读入的串（当作数）对N的不同的余数的等价类：,q0：余数为0的输入串的等价类； 该类数十进制为N*n+0,q1：余数为1的输入串的等价类；该类数十进制为N*n+1 q2：余数为2的输入串的等价类；该类数十进制为N*n+2, qN-1：余数为N-1的输入串的等价类；该类数十进制为N*n+N-1,注意,不能接收空串， 还需要一个开始状态qS,qS,读入x时，进入对应状态qi,本质,已知 qi(i =0，1，2，N-1) x=x1, x2,x3,xm 应该如何确定 j？,qi,qj,x,qi,已经读入的数为w，对应余数为i的输入串的等价类； 该类数十进制为N*n+i,当前读入的字符为x；则wx表示的十进制数为 (wx)10= base* (w)10 +x =base*（N*n+i）+x =N*base*n+base*i+x,该数对于N取余数就是base*i+x对于N的余数， 若该余数为j， 则相应的状态就应该从qi变换为qj,其中 i=0，1，2，N-1。 x = x1, x2,x3,xm 0, 1， ，base-1,例3-16构造DFA，接收,0，1上的语言 L=0n1m2k|n,m,k=1,该语言的串的特点是，0在最前面，1在中间，2在最后，0、1和2不能交叉，顺序也不能颠倒。 0、1和2的个数都至少为1个； 需要4个状态：,q0：开始状态,等待接收第1个0 q1：已经接收第1个0，负责接收可能的多个0，等待接收第1个1； q2：已经接收第1个1，负责接收可能的多个1，等待接收第1个2；,q3：已经接收第1个2，负责接收可能的多个2。,状态转移图(省略陷阱状态),q0,0,1,0,1,2,2,q1,q2,q3,思考1,补充陷阱状态及对应的状态函数。,思考2 DFA是否可以为(省略陷阱状态),q0,0,1,0,1,2,2,q1,q2,q3,.4 不确定的有限状态自动机,每个FSL都是右线性语言 (定理3-1),问题,每个右线性语言是不是一个FSL？,例,接收语言aa，ab的FA,省略陷阱状态,q1,a,b,q0,q2,a,a,q3,该自动机接收的语言L=aa，ab 是右线性语言； 但自动机不是DFA。,(q0，a)=q1，q2 即没有到达确定的惟一的状态。 不确定的有限状态自动机-NFA,3.4.1不确定的有限状态自动机,定义3-10 NFA是一个五元式， NFA =（Q，Q0，F） 其中： Q 是一个有限状态的集合 是字母表,Q0 Q 是开始状态集合 F Q 是接收状态集合,是Q2Q的状态转换函数 即 (q，a) 2Q NFA在状态q，扫描字母a后到达 可能的下一状态集合。,NFA与DFA,NFA有一个可能的开始状态集合和可能的下一状态集合 其余的同DFA。,NFA与DFA的重要区别在于 转移函数的不同。 (q，x)对应的是状态集合Q的一个子集,FA处于状态q,DFA对每个字母只有惟一的状态转移 NFA对某个字母可以有多个状态转移； NFA接收该字母时,从多个状态转移中可以 非确定地选择任意一个。,具体地,对于NFA， (q，a) Q (q，a) 有3种可能 (q，a) = (q，a) =q1 (q，a) =q1 ，q2，qn,或,或,(q，a)仍是一个状态转换函数，只是其值域发生了改变。 所有(q，a)对应的所有子集元素个数都为1时，NFA退化为DFA,NFA停机,NFA在两种情况下自动停机： 将输入串扫描结束 (q，a)=(即对应没有定义),或,在扫描一个串w时，NFA的状态发生转换，可能会有多种情况： 可能在接收状态时终止； 可能在非接收状态时终止； 也可能在中途停止（中止）。,若至少存在一条路径可以使NFA在扫描串w后到达接收状态 则串w能被NFA所接收。,对于字母表上的NFA，它能接收的所有串的集合，称为NFA能接收的语言。 记为 L(NFA),问题,如何形式化定义L(NFA)?,定义 NFA扩展状态转换函数,给定NFA，扩展的状态转换函数 *：2Q*2Q 为 *(p，w)= Q 即NFA在状态集合p时，扫描串w后到达可能的的状态集合Q,NFA扩展状态转换函数,若p= q1，q2，qn *（p，）=p,a,*(p，a) = (q，a)|qp =(q1, a),(q2, a),(qn, a),对于串w,w=a *(p， w) =*(p，a) = (q，a)| q*(p，),或,w= a *(p， w ) =*(p， a ) = *(q,)| q*(p， a ),L(NFA)表示被NFA所接收的语言 L(NFA)=w|w*且 *(Q0， w)F,它表示所有串w的集合 在NFA的状态图中，至少存在一条路径 以w为标记，能使NFA从某个开始状态到达某个接收状态。,构造NFA，分别接收语言,0*、 0+ (0+1)*、(0+1)+ 0、01 (0+1)*0 0(0+1) * 1 (0+1)*00(0+1)*,3.4.2 NFA的确定化,DFA可以转换为NFA NFA可以转换为DFA(确定化),定理3-3,*的一个子集L是一个FSL， 充要条件为 存在NFA，使得L(NFA)=L,证明：= 必要性,若L是FSL，则有L=L(DFA） DFA=(Q ， ， ， q0 ， F) 构造 NFA=(Q，1，q0，F),1(q，a)=(q，a) 即把DFA的一个状态 当作 NFA的一个状态集合 则 L=L(DFA)=L(NFA),证明: = 充分性,NFA=（Q，Q0，F） 语言L=L(NFA)* 构造 DFA=( Q,，q0，F) 其中 Q=2Q,q0= Q0Q F Q =p|pQ 且 pF,(p，a)= (q，a)|qp 其中, pQ，a 即(q1，q2，qn，a) =(q1,a),(q2，a),(qn，a),即把NFA的一个状态集合当作是DFA的一个状态。 则L=L(NFA)=L(DFA),NFA和DFA是可以互相转换的，是等价的； 接收的语言类都是FSL。,例3-18,a,a,b,S2,A,b,S1,a,b,NFADFA,S1和S2是开始状态 A是唯一的接收状态 该NFA共有3个状态,对于DFA，最多可能有8个状态： ，S1，S2，A，S1，A，S2，A，S1，S2，S1，S2，A,DFA状态转换函数,S1，S2,S2,A,S2,A,S2,A,A,A,A,A,A,DFA状态转换图,a,b,a,b,a,b,S1, S2,S2, A,A,注意：,若到达空集状态 实际上就是陷阱状态。,例3-19构造NFA，接收,0，1上的语言，该语言的每个字符串挡成二进制数时， 代表的数字能被2整除。,解1:直接构造DFA(以0结尾的串),0,q2,q1,q0,0,1,0,1,1,解2：,正则表达式为：(0+1)*0 直接构造NFA,0,1,q1,0,q0,转换为DFA,0,q1,0,q0,1,1,例3-20 接收,语言L= w|wa,b,c+, |w|1, w中最后字母与第一个字母相同,1)给出该语言的正则表达式； 2)构造NFA接受该语言； 3)将NFA转换为等价的DFA。,解,1) 该语言的正则表达式: a(a+b+c)*a + b(a+b+c)*b + c(a+b+c)*c,解,2)构造NFA接受该语言,解,3) 改造为DFA接受该语言： a b c q0 q1 q2 q3 q1 q1,q4 q1 q1 q2 q2 q2,q4 q2 q3 q3 q3 q3,q4 q1,q4 q1,q4 q1 q1 q2,q4 q2 q2,q4 q2 q3,q4 q3 q3 q3,q4,思考：构造NFA，接收,语言L= w|wa,b,c+, |w|0, w中最后字母与第一个字母相同 该语言的正则表达式: a(R)*a+b(R)*b+c(R)*c+a+b+c,例3-21接收,语言L= w| wa,b+, w中倒数第二个字母肯定在前面出现过,1)给出该语言的正则表达式； 2)构造NFA接受该语言； 3)将NFA转换为等价的DFA。,解,1) 该语言的正则表达式: (a+b)*a(a+b)*a(a+b) + (a+b)*b(a+b)*b(a+b),解,2)构造NFA接受该语言,解,3)将NFA转换为等价的DFA,例:构造NFA，接收,0，1上的语言; 该语言的每个句子必须包含00,正则表达式为： (0+1)*00(0+1)*,NFA,0,1,q2,0,q0,0,1,q1,0,构造NFA，接收,0，1上的语言， 该语言的每个句子必须包含001,正则表达式为：(0+1)*001(0+1)*,NFA,0,1,q2,001,q0,0,1,例3-23构造NFA，接收,0，1上的语言， 该语言每个句子必须不包含001,NFA,0,q1,0,1,1,q2,0,q0,例3-24构造NFA，接收,0，1上的语言， 该语言的每个句子 以0开头，以1结尾。,NFA,q2,0,q0,0,1,q1,1,例3-25构造NFA，接收,0，1上的语言，该语言的句子 若以1结尾,则该字符串长度为偶数 若以0结尾,则该字符串长度为奇数,NFA (无),q4,0,1,0,1,0,q3,q2,q1,1,思考,若还需要接收，如何构造NFA？,一般：,NFA适于构造（已知正则表达式）的语言： 满足条件 的语言 包含子串 以串开始或结束 (倒数)第个字母是 ,定理3-4,每个右线性语言(正则语言)是一个FSL。,证明,L是右线性语言，则L=L(G) G=（，V，S，P） 首先消除G中一般的产生式,构造NFA 将文法非终结符当作NFA的状态 增加一个接收状态q,NFA=(Q，Q0，F) 其中： Q=V U q Q0=S F=q,注意,若文法G中有S,即L 则开始状态S也是接收状态,(A，x)=B| AxB在P中 q|Ax在P中 所以，L=L(G)=L(NFA),而NFA又和DFA是等价的， 一个右线性语言也是一个FSL。,总之,右线性语言和FSL是等价的， 右线性文法产生右线性语言； 有限状态自动机接收FSL； 也都是正则集。,例3-26 构造NFA，接收,0，1上的语言 L=0n1m2k|n,m,k0,NFA状态转移图,q0,0,1,0,1,2,2,q1,q2,q3,或,q0,0,1,0,1,2,2,q1,q2,q3,例3-27构造NFA，接收,0，1上的语言 L=0n1m2k|n,m,k=0,0,1,0,1,2,2,q3,q0,q1,q2,2,1,2,或 多个开始状态的NFA,1,0,2,2,q3,q1,q2,1,2,3.5 带动作的有限状态自动机,对于FA（DFA、NFA），有 (q，)=q *(q，)=q (q，)=q *(P，)=P,表示FA不读入任何字母(即只扫描空串时)， FA的状态不发生改变，并且读头不进行移动，仍然指向当前非空字符。,若允许FA在不读入任何字符时,FA的状态可以发生改变， 则FA为带有动作的FA,定义3-14带动作的有限状态自动机,带有动作的FA是一个五元式, -FA=(Q，Q0，F) Q，Q0，F的含义同NFA,: Q 2Q (q，a) 2Q (q ，) 2Q,即,具体,(q,)=q 表示自动机在状态q时，不读入任何字母，自动机状态不变 并且读头不移动；,(q，a)= 表示自动机在读入字母a后，自动机停机。,(q，a)=p1，p2，p3，pm 表示自动机在读入字母a后，自动机的状态可以选择地改变为p1，p2，p3，或者pm 并将读头向右移动一个单元；,(q,)=q1，q2，q3，qn 表示自动机在状态q时，不读入任何字母，自动机的状态可以选择地改变为q1，q2，q3，或qn 并且读头不移动；,注意,带有动作的FA一定是NFA。 一般，记为-NFA。,例3-28,使用-NFA接收语言 L=0*1*2* 即 L=0n1m2k|n,m,k=0,状态图,0*1*2*,q0,q1,q2,2,0,1,对应的5个函数为： (q0，0)=q0 (q0，)=q1 (q1，1)=q1 (q1，)=q2 (q2，2)=q2,定义3-15,对于-NFA ，qQ 从q开始，扫描1个或多个后能够到达的状态集记为 -CLOSURE(q),-CLOSURE(q) = p|扫描后能够从q到达p,对于-NFA， qQ -CLOSURE(q)是由递归规则确定的状态集：,规则,(1) q-CLOSURE(q) 即任意状态q接收空串，至少都能保持状态q不变；,规则,(2) 如果p-CLOSURE(q) 则(p,) -CLOSURE(q) (3) 重复(2)，直到-CLOSURE(q)中的状态不再增加为止。,注意,-CLOSURE(q)与(q,)不同,进一步,对于状态集合P，定义 -CLOSURE(P) = ,qP,-CLOSURE（q）,定义3-16 扩展的状态转换函数,-NFA 扩展状态转换函数 *： 2Q *2Q为 *（P，w）= Q 即自动机在状态集合P时，扫描串w后到达的状态集合Q,空串,*(q,)=-CLOSURE(q) *(P,)=-CLOSURE(P),单个字母,*(q，a) =*(q，a) =-CLOSURE( (p,a) *(P，a)= *(q，a),qP,p*(q,),对于串wa,*(P,wa)=* (*(P,w),a),或,*(P,aw)=* (*(P,a),w),对于,-CLOSURE(q0)= -CLOSURE(q1)= -CLOSURE(q2)=,q0,q1，q2,q2,q1,q2,对于,*(q0,) =-CLOSURE(q0) =q0，q1，q2,*(q0,0) = *(q0, 0) =-CLOSURE( (p,0) p*(q0,) =-CLOSURE( (q0,0) (q1,0) (q2,0) =-CLOSURE(q0) =q0，q1，q2,*（q0,01） =* (*(q0,0),1) =* (q0,q1,q2,1) =-CLOSURE( (q0,1) (q1,1) (q2,1) =q1,q2,注意,*(q，)与(q，)不同,定理3-5,如果语言L被-NFA接收，则 该语言L也能够被一个NFA接收,证明 ：,假设语言L被一个-NFA接收, -NFA =(Q，Q0，F),1)构造 NFA1= (Q，1，Q0，F1) 其中:对于a 1(q，a)= *（q，a）,F1= Fq0 若 F-CLOSURE(q0) F1= F 若 F-CLOSURE(q0) =,2）证明对于w+,有 1(q0，w)= *（q0,w） ,结论,如果语言L被-NFA接收，则语言L也能够被一个NFA接收,例3-29,将-NFA改造为等价的NFA。,q0,q1,q2,2,0,1,q1,q0,q2,2,0,1,0,1,1,2,0,1,2,例3-30构造-NFA,接收,0，1上的语言 L=0k|k=0，k能够被2或3整除 即L=02n或03m |n,m=0,q0,q1,q3,q2,q4,q5,0,0,0,0,0,思考,L=02n+3m |n,m0,请验证,q0,q5,q1,0,q2,0,q3,0,q4,0,0,0,0,思考：,-NFA转换为NFA能否 先将-NFA转换为“右线性”文法，再转换为NFA？ 引进单产生式AB,3.6 有限状态自动机的一些变形,有限状态自动机存在变形。,3.6.1双向的有限状态自动机,在处理输入串的过程中， 双向的有限状态自动机的读头 可以向右移动一个单元； 也可以向左移动一个单元； 也可以不移动。,定义3-18,确定的双向的有限状态自动机(2DFA)是一个五元式： 2DFA =（Q，q0，F） 其中，Q,q0，F的含义同DFA,：状态转换函数； QQL，R，N 对于qQ，a,(q，a)=p，D,2DFA在状态q读入字母a 自动机状态将变为p状态 D=L 读头向左移动一个单元 D=R 读头向左移动一个单元 D=N 读头位置不变；,2DFA格局描述同DFA,2DFA =（Q，q0，F）接收的语言为L(2DFA) L( 2DFA)=w|q0w=*q，qF,定理3-6,2DFA与DFA等价。 证明： 略。,可以定义不确定的双向的有限状态自动机。,定义3-20,不确定双向有限状态自动机2NFA是一个五元式： 2NFA =(Q， Q0，F) 其中 Q， Q0 ，F的含义同NFA,：状态转换函数； ：Q2QL，R，N,对于qQ，a, D1，D2，DmL,R,N，,(q,a)=(p1,D1),(p2,D2),(pm,Dm) 2NFA在状态q读入字母a 可以将状态变为pi 按照Di实现对读头的移动,定理3-7,2NFA与NFA等价。 证明： 略。,3.6.2带输出的有限状态自动机,FA，对于某个输入串w 得到的结论是: 是否接收该串； 或FA输出 “是”或“否”。,存在许多有穷状态系统 对于不同的输入信号， 除系统内部的状态变化之外， 还向系统外部输出各种信号。,模型图,有限状态系统,输入序列,输入序列,典型带输出的有穷自动机-Moore机和Mealy机。 由于它们带有输出，从抽象的角度考虑，就没有必要再设置接收状态（集）。,定义3-21,Moore机是一个六元式： Moore M=(Q, q0) 其中 Q，q0，的含义同FA ：输出字母表,输出函数：Q 对于qQ，a (q)=a 表示Moore机处于状态q时输出a,Moore机,在读入输入串的过程中 状态不断发生改变 并且在每个状态上都有输出,对于输入串a1a2a3an-1an,设(q0,a1)= q1 (q1,a2)= q2 (qn-2,an-1)= qn-1 (qn-1,an)= qn,则,Moore机的输出序列可以表示为： (q0)(q1)(q2)(qn),如果输入串的长度为n,则Moore机的输出串的长度为n+1。,实际上,FA只是Moore机的一个特例。,若Moore机的输出仅只有F或T 将输出T的状态当作接收状态，Moore机就是一般的FA。,例3-31设计Moore机,=0，1 若将输入串当作二进制数，则在读入串的过程中， 希望输出已经读过的（数字）串模3的余数。,分析,模3的余数只能是0、1和2 输出字母表=0，1，2 状态q0、q1和q2对应3种余数,状态上的标记表示Moore机在该状态时的输出,q0,q1,q2,0,1,2,0,0,0,1,1,1,当输入为1010时 状态变换的序列为 q0 q1 q2 q2 q1 输出 0 1 2 2 1,即,当输入时，输出余数0 当输入1时，输出余数1 当输入10时，输出余数2 当输入101时，输出余数2 当输入1010时，输出余数1,定义3-2