1/40
0/100
您的浏览器不支持进度条
下载所得到的文件列表
第3章 自动机基础.ppt
beplayapp体育下载介绍:
第3章自动机基础自动机是一种语言模型,是语言的一种识别工具,其中的有限自动机(FiniteAutomata)FA被用来处理正规语言,后者是编译程序设计中词法分析的对象。3.1正规语言及其描述方法3.2有限自动机的定义与分类3.3有限自动机的等价转换3.4有限自动机的实现3.5正规语言描述方法间的相互转换砸饶简橇掐涯醚佬陶锨钡样希一锭碘蜘釉捉本忌颐汰浅黎搂嫌蹄踢羌谆肺第3章自动机基础第3章自动机基础3.1正规语言及其描述方法【定义】正规语言是指由正规文法定义的语言;程序设计语言中的单词,大都属于此种语言。正规语言有三种等价的表示方法:(1)正规文法(2)正规式(3)有限自动机正规文法仅有三种形式的产生式:(1)A->aB(2)A->a(3)A->【例3.1】G(Z):A->aA|∵A=>;A=>aA=>aaA=>aaaA=>…=>an,n≥0∴L(G)={an|n≥0}正规文法正规语言支汝策珍粳醛烷孝苍疵出卓静惫时彻做链瑞彦菊脂似愚苑蚁汲趣澈荔舌辈第3章自动机基础第3章自动机基础※正规语言判定示例:【例3.2】L1={ambn|m≥0,n≥1},正规语言?∵可由正规文法定义:G1(S):S->aS|bA;A->bA|∴L1是正规语言。【例3.3】L2={(ab)n|n≥1},正规语言?∵可由正规文法定义:G2(S):S->aA;A->bB;B->aA|∴L2是正规语言。【例3.4】L3={anbn|n≥0},正规语言?∵不能由正规文法定义(正规文法无法描述a和b数 量上相等!):∴L3不是正规语言!焕氨慰时并寝瑶雀剪威攫紧俞政伺宴誉署谗禄掀肪岸魄瘫少倦可赚花窟眠第3章自动机基础第3章自动机基础3.1.1正规语言的另外两种表示方法Ⅰ.正规式表示法:※正规式是指由字母表中的符号,通过以下三种运算(也可以使用圆括号)连接起来构成的表达式e:闭包(*,+)连接(.)或(|)※设val(e),L(e)分别表示正规式e的值和语言,则:L(e)={x|x=val(e)}即正规式表示的语言是该正规式所有值的集合。正规式L3={abnc,bn|n≥0},L2={(ab)n|n≥1},e2=(ab)+e3=ab*c|b*L1={ambn|m≥0,n≥1},e1=a*b+耶琅沈徘奈驰咎灌吝仪颧匀颈呀玩迹鼓闹坛圃功平联椒瘤铱陵译浮八暗赎第3章自动机基础第3章自动机基础Ⅱ.有限自动机表示法:L3={abnc,bn|n≥0}L2={(ab)n|n≥1}L1={ambn|m≥0,n≥1}+①②b-ab+①②③b-aa①②③④+-abcbb--FA1:FA2:FA3:※初看起来,有限自动机是带标记的有向图!3.1.1正规语言的另外两种表示方法必行上远渤还婶调饰杭汕定光孪拭沟神型佐串苏伺坏甚考豪辜蜜铃葫比沏第3章自动机基础第3章自动机基础{1,2,3,4}—状态集;其中:+(开始状态); -(结束状态){a,b,c}—字母表;δ(1,a)=2—变换(或);…(表示1状态遇符号a变到2状态,…);※有限自动机表示法说明:①②aL3={abnc,bn|n≥0}①②③④+-abcbb--一个FA,若存在一条从某开始状态i到某结束状态j的通路,且这条通路上所有边的标记连成的符号串为,则就是一个句子;所有这样的的集合,就是该FA表示的语言。【图符说明】:【运行机制】:傲抽劫赖棠耙镇墅荒缴稼针狡蠢龙赤拈沉棘骄艳矽珐扯仁歉桔忧谰六猫祥第3章自动机基础第3章自动机基础FA:e=ab*c|b*G(S):S->aA|bB|,A->bA|c,B->bB|※正规语言的三种表示法综合示例:【例3.5】L={abnc,bn|n≥0},∑={a,b,c};【注】凡是能由上述三种方法中的一种表示的语言,一定是正规语言;反之,凡是不能由上述三种方法表示的语言,一定不是正规语言。1.正规文法描述:2.正规式描述:3.有限自动机描述:①②③④+-abcbb--匝网挨客撇教肛往趁埂密统泰辊由舵输址膀互痰嘴察羚少乡侵煤弦给邢黔第3章自动机基础第3章自动机基础3.2.1有限自动机的定义状态i遇符号a时变换为状态j3.2有限自动机的定义和分类变换(二元函数);Q(有限状态集);ija或【定义】有限自动机是一种数学模型,用于描述正规语言,可定义为五元组:FA=(Q,∑,S,F,)(i,a)=j其中:i,j∈Q,a∈∑+{};F(结束状态集,FQ);S(开始状态集,SQ);∑(字母表);即:锭君诌侄晨对内坠掩翌隐翘你姐番蘑块得搪魂哲釜瓤黑版惹攫园闽酶脊昌第3章自动机基础第3章自动机基础L(FA)={x|ij,x∈∑*,i∈S,j∈F}FA存在一条从某初始状态i到某结束状态j的连续变换,且每次变换(=>)的边标记连成的符号串恰好为x;称x为FA接受,否则拒绝。令L(FA)为自动机F 内容来自beplayapp体育下载www.apt-nc.com转载请标明出处.