《编译原理》2.2第二章形式语言与自动机理论基础

《《编译原理》2.2第二章形式语言与自动机理论基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章形式语言与自动机理论基础2.2有限自动机FA(FiniteAutomata)关于有穷自动机我们将讨论如下题目：确定的有穷自动机DFA不确定的有穷自动机NFADFA与NFA的等价——NFA的确定化DFA的最小化1、确定的有限自动机DFADFA：DeterministicFiniteAutomata定义2.26一个确定的有限自动机M（记作DFAM)是一个五元组Ｍ＝（Ｑ，Σ，f，q0，Z）其中Ｑ是一个有限状态集合。Σ是输入字符的有限集合，它的每个元素是输入符号。q∈Ｑ，q称为初始状态。00ZＱ，Z称为终结状态集合。f

2、是一个从Ｑ×Σ到Ｑ的单值映射f(ｑ，ａ)＝ｑ（ｑ,ｑ∈Ｑ，ａ∈Σ）3例：(1)电梯的控制系统；(2)人的大脑也是有限控制系统；(3)计算机自身也是有限控制系统。注意：DFA是具有离散输入、输出系统的一个纯数学模型；DFA的技巧在于状态的设置；DFA映射的唯一性和初态的唯一性。4例:设ＤＦＡＭ＝（｛ａ,ｂ｝,｛０,１,２,３｝，f，０,｛３｝）其中f:f（０，ａ）＝１，f（１，ａ）＝3f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３a1aa0ba3b2bb5状态

3、转换图表示6DFA的三种表示1.转换函数；2.转移矩阵；3.状态转换图。设ＤＦＡＭ＝（｛ａ，ｂ｝，｛０，１，２，３｝，f，０，｛３｝）其中f:f（０，ａ）＝１，f（１，ａ）＝3f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３ab012转移矩阵易存储1322133338例:一个单部电梯对3层楼进行控制的电梯控制系统的DFA描述。问题分析：用户请求（输入）上1、上2、上3下1、下2、下3状态设置（所处楼层）1层——S12层——S23层——S39状态转换图状态

4、矩阵表示10DFAM接受的语言*∑上的符号串w被DFAM接受M=（Σ，Q,f，S，Z）若ω∑*，f(S，ω)=P，其中S为M的开始状态，PZ，Z为终态集。则称ω为DFAM所接受（识别）.确定的自动机M所识别的字符串的全体称为M识别的语言，记为L(M)练习：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画出状态图证明t=baab被DFAM所接受12aUaa，baQbV

5、b例：证明t=baab被DFA所接受。f（S，baab）=f（f（S，b），aab）=f（V，aab）=f（f（V，a），ab）=f（U，ab）=f（f（U，a），b）=f（Q，b）=QQ属于终态。13综述：(1)对于Σ上的任何字符α，如果存在一条从初态到某一终态结的路径，且该路径上所有弧的标记符连接成的字符等于α,则称α为DFAM所识别(接受)。(2)若DFA仅一个状态结点，该状态结点既是初态又是终态，则空字符集合{ε}为DFAM所接受。(3)一个DFAM所能接受的字符的全体记为L(M)。14DFA的确定性表现在其映射函数是

6、一个单值函数。但是实际问题中，映射函数往往是一个多值函数。例如，源程序中扫描到一个字母时，不同的语言对应多种情况：C语言中：标识符/%S//if/switch….NFA在实际中更具普遍性。15非确定的有限自动机NFAM定义2.27:非确定有限自动机Ｍ是一个五元组Ｍ＝（Ｑ，Σ，f，q，Z）0其中：Σ，Ｑ，Z同ＤＦＡq是一个初态集0f是一个从ＱΣ*到Ｑ的子集的映射，即f：ＱΣ*２Ｑ注意：后继状态不是惟一的16例：NFAN=({S,P,Z},{0,1},f,{S,P},{Z})其中f（S，0）={P}f（Z，0）

7、={P}f（P，1）={Z}f（Z，1）={P}f（S，1）={S，Z}画出状态图11S0,1Z10P17矩阵表示矩阵表示01S{P}{S,Z}0简化为P{}{Z}0Z{P}{P}101SPS,Z0P.Z0ZPP1练习：NFAN=({a,b},{0,1,2},f,0,{2})f（０，ａ）＝｛0,１}，f（１，ａ）＝Фf（２，ａ）＝Ф，f（2，b）＝Фf（０，ｂ）＝{0}，f（１，ｂ）＝{２}画出状态转换图aab012b19回顾：f为Q*到Q的子集（2Q）的一种映射具有转移的不确定的有穷自动机bca123例:给出一

8、个接收字符串aa*

9、bb*的NFAM，用状态转换图来表示。21NFA和DFA的区别22FA的等价性DFAN是NFAM的一个特例定理2.1：对任何一个NFAM，都存在一个D