《有穷自动机》PPT课件.ppt

《《有穷自动机》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Compiler编译原理Wednesday,March13,2013（1）分析和识别单词及属性，包括识别语言的关键字、标识符、常数、运算符等；（2）跳过各种分隔符，如空格，回车，制表符等；（3）删除注释；（4）进行词法检查，报告所发现的错误；（5）建立符号表。词法分析的任务Compiler编译原理Wednesday,March13,2013有穷自动机标识符无符号整数单界符双界符S1非字母数字字母字母、数字2非数字数字数字3其他字符+*，（）出口4其他字符<5=非=出错其他读字符查保留字表返回S状态图的形式化描述Compiler编译原理W

2、ednesday,March13,2013有穷自动机是一种数学模型，具有离散的输入与输出，系统可处于有穷状态中的任何一个它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具有穷自动机分为两类：确定的有穷自动机（DFA）(DeterministicFiniteAutomata)不确定的有穷自动机（NFA）(NondeterministicFiniteAutomata)Compiler编译原理Wednesday,March13,20132型文法（不确定的

3、下推自动机）1型文法（不确定的界限自动机）0型文法（图灵机）3型文法（有限自动机）Compiler编译原理Wednesday,March13,20131.确定的有穷自动机（DFA）M=(Σ,Q,f,S,Z)Σ：有穷字母表，它的每个元素称为一个输入符号Q：有穷集，它的每个元素称为一个状态S∈K，是唯一的初态Z⊂K是一个终态集，终态也称可接受状态或结束状态f是转换函数，是Q×Σ→Q上的单值映射：f（q1，a）=q2Compiler编译原理Wednesday,March13,2013状态转移函数f可用一矩阵来表示：输入字符状态ab01213

4、2213333例如:M:（{0,1,2,3},{a,b},f，0，{3}）f（0，a）=1f（0，b）=2f（1，a）=3f（1，b）=2f（2，a）=1f（2，b）=3f（3，a）=3f（3，b）=3所谓确定的状态机，其确定性表现在状态转移函数是单值函数！字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。M=(Σ,Q,f,S,Z)Compiler编译原理Wednesday,March13,2013一个DFA也可以用一状态转换图表示：输入字符状态ab012132213333DFA的状态

5、图表示：1032aabba,bba字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。Compiler编译原理Wednesday,March13,2013换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串α，则称α为DFAM（接受）识别。DFAM所接受的语言为：L(M)={α

6、f(S,α)=Sn,Sn∈Z}DFAM所能接受的符号串的全体记为L(M)若M的初态结点同时为终态，或者存在一条从初态到某个终态结点的ε通路，则ε为M所识别。Compiler编译原

7、理Wednesday,March13,2013δ（0，abaab）=δ（1，baab）=δ（2，aab）=δ（1，ab）=δ（3，b）=3(接受)DFA的状态图表示：1032aabba,bbaδ（0，abab）=δ（1，bab）=δ（2，ab）=δ（1，b）=2(拒绝)对于符号串abaab对于符号串ababCompiler编译原理Wednesday,March13,2013f是一个多值函数，是从Q×Σ*到Q的子集的映射：f：Q×Σ→2Q其中2Q是Q的幂集，即Q中所有子集组成的集合。2.不确定的有穷自动机（NFA）M=(Σ,Q,f,S,

8、Z)有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的Compiler编译原理Wednesday,March13,2013例：NFAN=({a,b,c},{1,2,3,4},f,{1},{4})符号状态εabc1{4}{2，3}ΦΦ2Φ{2}{4}Φ3ΦΦΦ{3，4}4ΦΦΦΦCompiler编译原理Wednesday,March13,2013对于Σ*上的任何符号串α，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字符依次连接成的串等于α，则称α可以被NFAN所识别或接受。若N

9、的初态结点同时为终态，或者存在一条从初态到某个终态结点的ε通路，则ε为N所识别。NFAN所能识别的符号串的全体记为L(N)，称为NFAN所识别的语言Compiler编译原理Wednesday,March13