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