计算引论 有限自动机

计算引论有限自动机第1页，共24页，2023年，2月20日，星期四第三章文法与语言3.1集合关系语言3.2有限自动机3.3上下文无关语言3.4上下文无关语言识别算法第2页，共24页，2023年，2月20日，星期四3.2有限自动机问题提出:如何构造可以接受及产生一个语言的计算模型?语言识别器:对一个已经存在的字符串集合,如何判断它就是符合条件的语言?解决接受的问题语言产生器:怎样根据正则表达式产生一个语言.解决产生的问题第3页，共24页，2023年，2月20日，星期四3.2有限自动机有限状态图正则表达式可以用有向图表示，图的结点是状态，有一个起始结点和一个终止结点。起始结点只有出边，终止结点用双圆圈表示。边上的符号表示从一个状态到另一个状态结点允许出现的字符，这种图称之为有限状态图。正则式01*

对应的有限状态图为：第4页，共24页，2023年，2月20日，星期四3.2有限自动机例：打电话的过程，在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用五个状态来表示。q0q1q2q3q4摘机收到拨号音拨号收应答信号挂机收齐号码q0:空闲状态q1:等待拨号状态q2:可以拨号状态q3:等待应答状态q4:通话状态第5页，共24页，2023年，2月20日，星期四3.2有限自动机有限自动机(Finiteautomaton):对实际计算机的一个严格限制的模型与实际计算机的共同之处是有一个固定的,计算能力有限的中央处理器.第6页，共24页，2023年，2月20日，星期四3.2有限自动机特点:以字符串作为输入,通过输入带传送字符串;除了提示输入的字符串是否接受外,没有任何其他的输出;在它的固定中央处理器的外面完全没有记忆功能;类似一个语言识别器.第7页，共24页，2023年，2月20日，星期四3.2有限自动机有限自动机的构造abababab有限控制器q0q5q4q3q1q2输入带读头第8页，共24页，2023年，2月20日，星期四3.2有限自动机组成:输入带:放字符串的装置有限控制器:含不同的内部状态读写头原理:在一定的时间间隔内,自动机根据从输入带上读入的符号和当前的内部状态,进入一个新的状态.第9页，共24页，2023年，2月20日，星期四3.2有限自动机过程:读取一个符号后,读写头向右移动一个方格,读取下一个符号,有限控制器的内部状态发生改变.最终读写头到达输入串的尽头.自动机将根据它所处的状态来说明它是否接受读入的字符串,如果此时的状态正好是一个最终状态,则认为该字符串是可接受的.第10页，共24页，2023年，2月20日，星期四3.2有限自动机根据每次转换后的状态是否唯一,可将有限自动机分为确定型有限自动机和非确定型有限自动机,本课程只介绍确定型有限自动机.第11页，共24页，2023年，2月20日，星期四3.2有限自动机定义:确定型有限自动机为一个五元组M=(Q,∑,,s,F),其中Q为状态的有限集合∑为字母表sQ为起始状态FQ为终止状态集为Q∑Q的转换函数第12页，共24页，2023年，2月20日，星期四3.2有限自动机转换函数说明了自动机M下一步将进入的状态.若M当前状态为qQ,从输入带上读入的符号为a∑,则(q,a)Q为Q中唯一确定的状态.第13页，共24页，2023年，2月20日，星期四3.2有限自动机格局:机器的状态(有限控制器,读写头和输入带)的表示方式.连续时刻的格局序列就是自动机在输入字符串上的计算(computation).格局是由当前状态和字符串未输入部分决定,即确定型有限自动机(Q,,,s,F)的格局是Q*中任意一个元素.例如上图中的格局为(q2,ababab)第14页，共24页，2023年，2月20日，星期四3.2有限自动机若M的一个格局经过一步(读写头)的移动到达另一个格局,则称这两个格局之间有二元关系⊢M.例如,若(q,w)和(q’,w’)为M的格局,当且仅当对某a∈有w=aw’及(q,a)=q’时有(q,w)⊢M(q’,w’).此时称(q,w)一步产生(q’,w’).第15页，共24页，2023年，2月20日，星期四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).第16页，共24页，2023年，2月20日，星期四3.2有限自动机例,令M为确定型有限自动机(Q,,,s,F),其中Q={q0,q1},={a,b},s=q0,F={q0},为如右表所示qw(q,w)q0aq0q0bq1q1aq1q1bq0第17页，共24页，2023年，2月20日，星期四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接受第18页，共24页，2023年，2月20日，星期四a>3.2有限自动机状态图状态用结点表示,用标有b的从q0指向q1的箭头表示(q0,b)=q1,终止状态用双圆圈表示,起始状态用>表示q0bbq1a第19页，共24页，2023年，2月20日，星期四3.2有限自动机例,设计一个确定型有限自动机M,可以接受语言:L(M)={v{a,b}*:v不含三个连续的b}第20页，共24页，2023年，2月20日，星期四3.2有限自动机

令M=(Q,∑,,s,F),其中Q={q0,q1,q2,q3}∑={a,b},s=q0,F={q0,q1,q2}表格表示如下:第21页，共24页，2023年，2月20日，星期四3.2有限自动机qw(q,w)q0aq0q0bq1q1aq0q1bq2q2aq0q2bq3q3aq3q3bq3第22页，共24页，2023年，2月20日，星期四baq3>3.2有限自动机只要读入a,M的状态如果为q0,q1或q2,M都会到达q0状态q0,q1和q2都为终止状态,