有限自动机理论CH3PART.ppt

第三章,有限状态自动机,定义语言,可以从两个方面进行： ）从产生语言的角度； ）从接收(或识别)语言的角度。,形式语言研究内容,产生一个语言: 1)定义语言中的基本句子; 2)根据其余句子的形成规则，产生出该语言所包含的所有句子。,有限自动机研究内容,使用某种自动机模型来接收字符串 接收的所有字符串形成的集合，也是一个语言,统一的理论,形式语言与自动机作为统一的理论,实际上包括3个方面的内容: 1) 形式语言理论(产生语言) 2) 自动机理论(接收语言) 3) 形式语言与自动机的等价性理论,有限状态自动机 FA (Finite state Automaton),FA是为研究 有限存储的计算过程 正则语言 而抽象出的一种计算模型。,两类有限状态自动机,接收器 判断是否接收输入串； 转换器 对给定输入产生输出。,FA还可以分成确定（DFA）与非确定（NFA）两种。,等价性,有限状态自动机识别的语言称为有限状态语言-FSL. 从产生语言角度而言， FSL就是右线性语言-RLL 从正则运算角度而言， FSL就是正则语言-RL。,有限状态自动机除了它在理论上的价值外， 还在数字电路设计、词法分析、文本编辑程序等领域得到广泛应用,3.1 有限状态自动机,有限状态自动机是具有离散输入和输出系统的一种数学模型。,有限状态自动机物理模型,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=(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 有向边的数目就是状态转换函数的个数。,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将输入串扫描结束时 (自动)停机,注意1：,DFA将输入串扫描结束停机时， 如果DFA处于某一个接收状态， 则表示接收整个输入串； 反之，则表示不接收整个输入串;,注意2：,对于状态q,如果不能识别字母a 则将状态转换到一个特殊的状态：陷阱状态qt 即 (q，a)=qt,陷阱状态qt不能够改变为其他状态 即 对于a (qt ，a)=qt,构造DFA，分别接收语言,0，1* 0，1+ 0 =0 01,定理3-1,每个FSL都是一个右线性语言 分析： 已知 接收FSL的DFA 构造 右线性文法产生该FSL,证明思路,状态转换函数和产生式的等价作用 (q, a)=q AaB 接收a 产生a 状态变化 非终结符号变化 结论:DFA状态等价于文法非终结符,思考,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) DFA3接收的语言是L1的补 L3=L(DFA3) 也是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的开始状态只负责识别输入串的第一个字母； 文法的开始符号只负责串的推导的开始； 优点是？,状态图为,1,0,qs,0,1,0,0,0,1,q1,q2,q3,q0,1,1,例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 考查题 1,例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)，n=0,1,2， 应该如何确定 j？,qi,qj,n,扫描子串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),该关系是集合*上的一个等价关系，利用该关系， 可以将*划分为不多于|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是当前读入的输入串； qS：在开始状态 读入0时，w=0，进入状态q0； 读入1时，w=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的余