第3章 自动机基础.ppt

第3章自动机基础自动机是一种语言模型,是语言的一种识别工具,其中的有限自动机(FiniteAutomata)FA被用来处理正规语言,后者是编译程序设计中词法分析的对象。【定义】正规语言是指由正规文法定义的语言;程序设计语言中的单词,大都属于此种语言。正规语言有三种等价的表示方法:(1)正规文法(2)正规式(3)有限自动机正规文法仅有三种形式的产生式:(1)A->aB(2)A->a(3)A->【】G(Z):A->aA|∵A=>;A=>aA=>aaA=>aaaA=>…=>an,n≥0∴L(G)={an|n≥0}正规文法正规语言支汝策珍粳醛烷孝苍疵出卓静惫时彻做链瑞彦菊脂似愚苑蚁汲趣澈荔舌辈第3章自动机基础第3章自动机基础※正规语言判定示例:【】L1={ambn|m≥0,n≥1},正规语言?∵可由正规文法定义:G1(S):S->aS|bA;A->bA|∴L1是正规语言。【】L2={(ab)n|n≥1},正规语言?∵可由正规文法定义:G2(S):S->aA;A->bB;B->aA|∴L2是正规语言。【】L3={anbn|n≥0},正规语言?∵不能由正规文法定义(正规文法无法描述a和b数 量上相等!):∴L3不是正规语言!Ⅰ.正规式表示法:※正规式是指由字母表中的符号,通过以下三种运算(也可以使用圆括号)连接起来构成的表达式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:※初看起来,有限自动机是带标记的有向图!{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|※正规语言的三种表示法综合示例:【】L={abnc,bn|n≥0},∑={a,b,c};【注】凡是能由上述三种方法中的一种表示的语言,一定是正规语言;反之,凡是不能由上述三种方法表示的语言,一定不是正规语言。:::①②③④+-abcbb--变换(二元函数);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