编译原理第二章_(3).ppt

《编译原理第二章_(3).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.3有限自动机FA（FiniteAutomata)自动机:表示无穷字符串集合的工具。自动机字符串集合。有限自动机的描述能力与乔姆斯基体系中的3型文法是等价的。描述程序设计语言中的单词，进一步为词法分析程序的自动构造寻找特殊的方法和工具。它不能用来描述表达式、语句等复杂的语法结构。主要内容：确定有限自动机DFA确定有限自动机DFA的实现非确定有限自动机NFANFA到DFA的转换DFA的化简2.3.1确定有限自动机（DFA：DeterministicFiniteAutomata)一.确定有限自动机的定义确定有限自动机M为

2、一个五元组:M=(S,,s0,f,Z)，其中：S是一个有穷状态集，它的每个元素称为一个状态；是一个有穷字母表，它的每个元素称为一个输入字符；s0S，是唯一的一个初始状态(开始状态)；f是状态转换函数:SS，且单值函数。f(Si,a)=Sk表示：当前状态为Si，遇输入字符a时，自动机将唯一地转换到状态Sk，称Sk为Si的一个后继状态;ZS，是终止状态集（可接受状态集、结束状态集），其中的每个元素称为终止状态（可接受状态、结束状态）,Z可空。二、一个DFA的例子DFAM=({S,U,V,Q},{a,b},f,

3、S,{Q}),其中f定义为：f(S,a)=Uf(V,a)=Uf(S,b)=Vf(V,b)=Qf(U,a)=Qf(Q,a)=Qf(U,b)=Vf(Q,1)=Q三.DFA的两种表示方式状态转换图：用有向图表示自动机1.结点表示状态：1.1非终止状态由单圆圈围住的状态标识来表示;1.2终止状态由双圆圈围住的状态标识来表示（或由单圆圈围住的状态标识并标识以“-”来表示）；1.3开始状态由一个箭头指向的状态结点来表示(或标识以“+”来表示)。2.状态转换函数用有向边来表示，若f(Si,a)=Sk，则由表示Si的状态节点到表示Sk

4、的状态节点发出一条标识为a的有向边。DFAM=({S,U,V,Q},{a,b},f,S,{Q}),其中f定义为：f(S,a)=Uf(V,a)=Uf(S,b)=Vf(V,b)=Qf(U,a)=Qf(Q,a)=Qf(U,b)=Vf(Q,b)=Q状态转换图USVQaababab,bDFAM=({S,U,V,Q},{a,b},f,S,{Q}),其中f定义为：f(S,a)=Uf(V,a)=Uf(S,b)=Vf(V,b)=Qf(U,a)=Qf(Q,a)=Qf(U,b)=Vf(Q,b)=Q状态转换图USVQaababab,b三、DF

5、A接受的字符串对于*中的任何字符串t,若存在一条从初始结点到某一终止结点的路径，且这条路上所有弧上的标记符连接成的字符串等于t,则称t可为DFAM所接受（识别）。若DFAM的初始状态同时又是终止状态，则空字符串可为DFAM所接受（识别）。DFAM所能接受的字符串的全体记为L(M).例1：L(M1)={aba,abaa,abab,abaab,…}DFAM10123abaa,babaCurrentCharCurrentStateCurrentStateCurrentCharCurrentStateCurrentCharC

6、urrentStateCurrentChar例2：L(M2)={a,ab,abb,abbb,…}DFAM201ab例3：L(M3)={,b,bb,bbb,…}DFAM31b状态转换矩阵：用二维数组描述DFA转换矩阵的行表示确定有限自动机的状态;标识初始状态和终止状态：一般约定，第一行表示开始状态S0，或在右上角标注“+”；右上角标有“*”或“-”的状态为终止状态；转换矩阵的列表示确定有限自动机的输入字符；矩阵元素表示确定有限自动机的状态转换函数。DFAM=({S,U,V,Q},{a,b},f,S,{Q}),其中f定义

7、为：f(S,a)=Uf(V,a)=Uf(S,b)=Vf(V,b)=Qf(U,a)=Qf(Q,a)=Qf(U,b)=Vf(Q,1)=Q输入字符状态abS+UVUQVVUQQ*QQ五、陷阱状态例4:设有DFAM=（{0,1,2,3},{a,b,c},f,{0},{3}）其中f定义为：f(0,a)=1f(0,b)=4f(1,a)=4f(1,b)=2f(2,a)=3f(2,b)=4f(3,a)=3f(3,b)=3f(4,a)=4f(4,b)=40123abaa,b4a,babbΣSab0+112233*334444440123

8、abaa,b4a,babb0123abaa,bΣSab0+112233*33444444五、DFA的确定性初始状态唯一。状态转换函数f:SS是一个单值函数，也就是说，对任何状态sS,和输入符号a,f(S,a)唯一地确定了下一个状态，即至多确定一个状态。六、DFA的实现1状态转换矩阵的形式：1.当前状态State置为初始