计算引论6-有限自动机课件

第三章 文法与语言n3.1 集合关系语言n3.2 有限自动机n3.3 上下文无关语言n3.4 上下文无关语言识别算法第三章 文法与语言3.1 集合关系语言13.2 有限自动机有限自动机n问题提出:如何构造可以接受及产生一个语言的计算模型?n语言识别器:对一个已经存在的字符串集合,如何判断它就是符合条件的语言?解决接受的问题n语言产生器:怎样根据正则表达式产生一个语言.解决产生的问题3.2 有限自动机问题提出:如何构造可以接受及产生一个语23.2 有限自动机有限自动机 有限状态图 正则表达式可以用有向图表示，图的结点是状态，有一个起始结点和一个终止结点。起始结点只有出边，终止结点用双圆圈表示。边上的符号表示从一个状态到另一个状态结点允许出现的字符，这种图称之为有限状态图。正则式01*对应的有限状态图为：3.2 有限自动机 有限状态图33.2 有限自动机有限自动机n例：打电话的过程，在一次呼叫中，从建立连接到通话例：打电话的过程，在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用五个状态来表示。以分别用五个状态来表示。q q0 0q q1 1q q2 2q q3 3q q4 4摘机摘机收到拨号音收到拨号音拨号拨号收应答信号收应答信号挂机挂机收齐号码收齐号码q q0 0:空闲状态空闲状态q q1 1:等待拨号状态等待拨号状态q q2 2:可以拨号状态可以拨号状态q q3 3:等待应答状态等待应答状态q q4 4:通话状态通话状态3.2 有限自动机例：打电话的过程，在一次呼叫中，从建立连43.2 有限自动机有限自动机有限自动机(Finite automaton):n对实际计算机的一个严格限制的模型n与实际计算机的共同之处是有一个固定的,计算能力有限的中央处理器.3.2 有限自动机有限自动机(Finite automat53.2 有限自动机有限自动机特点:1.以字符串作为输入,通过输入带传送字符串;2.除了提示输入的字符串是否接受外,没有任何其他的输出;3.在它的固定中央处理器的外面完全没有记忆功能;4.类似一个语言识别器.3.2 有限自动机特点:63.2 有限自动机有限自动机n有限自动机的构造abababab有限控制器q0q5q4q3q1q2输入带读头3.2 有限自动机有限自动机的构造abababab有限控制73.2 有限自动机有限自动机n组成:1.输入带:放字符串的装置2.有限控制器:含不同的内部状态3.读写头n原理:在一定的时间间隔内,自动机根据从输入带上读入的符号和当前的内部状态,进入一个新的状态.3.2 有限自动机组成:83.2 有限自动机有限自动机过程:n读取一个符号后,读写头向右移动一个方格,读取下一个符号,有限控制器的内部状态发生改变.最终读写头到达输入串的尽头.n自动机将根据它所处的状态来说明它是否接受读入的字符串,如果此时的状态正好是一个最终状态,则认为该字符串是可接受的.3.2 有限自动机过程:93.2 有限自动机有限自动机n根据每次转换后的状态是否唯一,可将有限自动机分为确定型有限自动机和非确定型有限自动机,本课程只介绍确定型有限自动机.3.2 有限自动机根据每次转换后的状态是否唯一,可将有限103.2 有限自动机有限自动机n定义:确定型有限自动机为一个五元组M=(Q,s,F),其中nQ为状态的有限集合n为字母表nsQ为起始状态nFQ为终止状态集n为QQ的转换函数3.2 有限自动机定义:确定型有限自动机为一个五元组113.2 有限自动机有限自动机n转换函数说明了自动机M下一步将进入的状态.n若M当前状态为q Q,从输入带上读入的符号为a,则(q,a)Q为Q中唯一确定的状态.3.2 有限自动机转换函数说明了自动机M下一步将进入的状态123.2 有限自动机有限自动机n格局:机器的状态(有限控制器,读写头和输入带)的表示方式.n连续时刻的格局序列就是自动机在输入字符串上的计算(computation).n格局是由当前状态和字符串未输入部分决定,即确定型有限自动机(Q,s,F)的格局是Q*中任意一个元素.n例如上图中的格局为(q2,ababab)3.2 有限自动机格局:机器的状态(有限控制器,读写头133.2 有限自动机有限自动机n若M的一个格局经过一步(读写头)的移动到达另一个格局,则称这两个格局之间有二元关系M.n例如,若(q,w)和(q,w)为M的格局,当且仅当对某a有w=aw及(q,a)=q时有(q,w)M(q,w).此时称(q,w)一步产生(q,w).3.2 有限自动机若M的一个格局经过一步(读写头)的移动到143.2 有限自动机有限自动机nM的自反传递闭包表示为*M;用(q,w)*M(q,w)表示(q,w)经过多步(包括0步)后产生了(q,w).n字符串w*被M接受当且仅当存在状态qF,使得(s,w)*M(q,e).n所有由被M接受的字符串组成的集合即为M接受的语言,记为L(M).3.2 有限自动机M的自反传递闭包表示为*M;用(q153.2 有限自动机有限自动机n例,令M为确定型有限自动机(Q,s,F),其中Q=q0,q1,=a,b,s=q0,F=q0,为如右表所示qw(q,w)q0aq0q0bq1q1aq1q1bq03.2 有限自动机例,令M为确定型有限自动机(Q,163.2 有限自动机有限自动机n若输入为aabba,M的初始格局为(q0,aabba)则有 (q0,aabba)M(q0,abba)M(q0,bba)M(q1,ba)M(q0,a)M(q0,e)即(q0,aabba)*M(q0,e),因此aabba被M接受3.2 有限自动机若输入为aabba,M的初始格局为(q17a3.2 有限自动机有限自动机n状态图 状态用结点表示,用标有b的从q0指向q1的箭头表示(q0,b)=q1,终止状态用双圆圈表示,起始状态用表示q0bbq1aa3.2 有限自动机状态图q0bbq1a183.2 有限自动机有限自动机n例,设计一个确定型有限自动机M,可以接受语言:L(M)=v a,b*:v不含三个连续的b3.2 有限自动机例,设计一个确定型有限自动机M,可以193.2 有限自动机有限自动机n 令M=(Q,s,F),其中n Q=q0,q1,q2,q3n =a,b,n s=q0,n F=q0,q1,q2n 表格表示如下:3.2 有限自动机 令M=(Q,s,F203.2 有限自动机有限自动机qw(q,w)q0aq0q0bq1q1aq0q1bq2q2aq0q2bq3q3aq3q3bq33.2 有限自动机qw(q,w)q0aq0q0bq1q21baq33.2 有限自动机有限自动机n只要读入a,M的状态如果为q0,q1或q2,M都会到达q0n状态q0,q1和q2都为终止状态,所以任何不包含三个连续b的输入字符串都可以被接受.一旦出现三个连续b,M会进入q3状态,即死亡状态.aq0abbbaq1q2baq33.2 有限自动机只要读入a,M的状态如果为q223.2 有限自动机有限自动机n定理:语言是正规的当且仅当它可以被有限自动机接受3.2 有限自动机定理:语言是正规的当且仅当它可以被有限23