第02章形式语言与自动机理论(机械工业).

第二章形式语言与自动机理论基础主要内容：语言和文法有限自动机正则表达式语言和文法语言和文法的关系什么是语言？如何表述语言？什么是程序设计语言？如何表述程序设计语言？语言和文法基本概念字母表：元素的非空有穷集合。符号串：由字母表中的符号组成的任何有穷序列。或者如下定义：1.空符号串ε是上的符号串2.若x是上的符号串,a是的元素,则xa是上的符号串3.y是上的符号串,当且仅当它可以由1和2导出思考如下问题：1.符号串的长度如何定义？2.{ε}和有何区别？3.如何判断两个符号串相等？符号串的连接：设x和y均是字母表∑上的符号串，它们的连接是把y的所有符号顺序接在x的符号之后所得到的符号串。符号串的方幂：设x是字母表∑上的符号串，把x自身连接n次得到的符号串z,称作符号串x的n次幂，记作z=xn，特别地：x0=前缀和后缀：设x是字母表上的符号串，x=yz,则y是x的前缀，z是x的后缀，特别是当z≠时，y是x的真前缀；y≠ε时，z是x的真后缀。子字符串：非空字符串x,删去它的前缀和后缀后所得到的字符串称为x的子字符串，简称子串。如果删去的前缀和后缀不同时为ε,则称该子串为真子串。语言和文法符号串集合：若集合A中的所有元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。符号串集合的乘积：设A、B是两个符号串集合，AB表示A与B的乘积，则定义AB={xy|(x∈A)∧(y∈B)}符号串集合的方幂：设A是符号串集合，则称Ai是符号串集合A的方幂，其中i是非负整数。A0={},A1=A,A2=AA,…,An=AA…A符号串集合的正闭包：A+=A1∪A2∪A3…符号串集合的星闭包：A*=A0∪A1∪A2∪A3…语言和文法文法之概述文法能清晰地描述程序设计语言的语法构成易于理解。文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，以及检查出语法错误。基于文法实现的语言易于扩展语言和文法文法之定义文法G定义为四元组(VT,VN,S,P)VT是有限的终极符集合VN是有限的非终极符集合S是开始符，SVNP是产生式的集合，且具有下面的形式：，其中，(VTVN)*语言和文法文法之分类O型文法:也称为短语文法，其产生式具有形式:→，其中,(VTVN)*，并且至少含一个非终极符。1型文法:也称为上下文相关文法。它是0型文法的特例，要求||||(S→例外，但S不得出现于产生式右部)。2型文法:也称为上下文无关文法。它是1型文法的特例，即要求产生式左部是一个非终极符:A→。3型文法:也称为正则文法。它是2型文法的特例，即产生式的右部至多有两个符号，而且具有下面形式之一:A→a，A→aB其中A,BVN，aVT。语言和文法上下文无关文法（CFG）定义为四元组(VT,VN,S,P)VT是有限的终极符集合VN是有限的非终极符集合S是开始符，SVNP是产生式的集合，且具有下面的形式：AX1X2…Xn其中AVN，Xi(VTVN)，右部可空。语言和文法文法相关概念推导（直接推导）：如果A是一个产生式，则有A,其中表示一步推导(用A→)。这时称是由A直接推导的。的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串。+:表示通过一步或多步可推导出*:表示通过0步或多步可推导出语言和文法句型：如果有S*，则称符号串为CFG的句型。我们用SF(G)表示文法G的所有句型的集合。句子：如果只包含终极符，则称为CFG的句子。语言：L(G)={u|S+u,uVT*}文法G所定义的语言是其开始符所能推导的所有终极符号串(句子)的集合。最左（右）推导：如果进行推导时选择的是句型中的最左(右）非终极符，则称这种推导为最左(右)推导，并用符号lm（rm）表示最左（右）推导。左（右）句型：用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型(规范句型)。结论：每个句子都有相应的最右和最左推导（但对句型此结论不成立）短语：设S是文法的开始符，是句型(即有S*），如果满足条件：S*AA+则称是句型的一个短语。直接短语（简单短语）：如果满足条件：S*AA则称是句型的一个简单短语。句柄：一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。语言和文法语法分析树(简称分析树)用来描述句型的结构，是句型推导的一种树型表示。文法G=(VN,VT,S,P)，则称满足下面条件的树为G的一棵分析树：1.每个结点都有G的一个文法符号，并且根结点标有初始符S，非叶结点标有非终极符，叶结点标有终极符或非终极符或。2.如果一个非叶结点A有n个儿子结点(从左到右）为X1,X2,...,Xn，则G一定有产生式A→X1X2...Xn。线性推导：我们称用符号进行的推导为线性推导。树型推导与线性推导的不同：线性推导指明了推导的顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵分析树(如果无二义性)，而线性推导则可很多。语言和文法二义性文法：如果一个文法的某个句型有两棵不同的语法分析树，则称该文法二义性为二义性文法。文法G=({+,*,I,(,)},{E},E,P),其中P为：EiEE+EEE*EE(E)句型i*i+i:推导1:EE+EE*E+Ei*E+Ei*i+Ei*i+i推导1:EE*Ei*Ei*E+Ei*i+Ei*i+i推导1的语法树E+EEE*EiiiEE*EE+Eii推导2的语法树i语言和文法文法等价变换增加拓广产生式定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2的开始符唯一且不出现于任何产生式的右部。证明：假设S是G1的开始符，则只要在G1中扩充一条新产生式ZS即可，其中Z是新的开始符。另这样扩充后的文法为G2，则它显然满足定理的要求。消除空产生式定理：对任一文法G1，可构造文法G2，使得L(G1)=L(G2)，且G2中无空产生式。证明：根据G1，构造G2的方法如下：(1)令={A|A}(2)={A|A+,+}。(3)从G1中删除所有空产生式。(4)从G1中删除只能导出空串的非终极符。(5)对于文法中任意产生式AX1X2…Xi-1XiXi+1…Xna.若XiVT，不做动作；b.若XiVN-，不做动作；c.若Xi，补充规则AX1X2…Xi-1Xi+1…Xn；例：AaBcDBb|DBB|d消除不可达产生式定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2中的每个非终极符必出现在它的某个句型中。证明：根据G1，构造文法G2的方法如下：(1)令={Z|Z是文法的开始符}。(2)递归扩充直到收敛为止，即={B|AxByG1,BVN,A}(3)若一个产生式左部非终极符A，则删除以A为左部的所有产生式。消除特型产生式定理：对任一文法G1，可以构造文法G2，使得L(G1)=L(G2)，且在G2中没有特型产生式。证明：构造无特型产生式的文法G2的方法如下：(1)对文法G1中任意非终极符A，求集合A={B|A+B,BVN}。(2)若BA，且B是文法G中的一个非特型产生式，则补充如下规则A。(3)去掉文法G1中的所有的特型产生式。(4)去掉新的文法中的无用产生式。例：AB|D|aBBC|bCcDB|d消除文法二义性SifEthenS|ifEthenSelseS|Other该文法是一个二义性文法，与之等价的无二义性的文法如下：SM|UMifEthenMelseM|OtherUifEthenS|ifEthenMelseU消除公共前缀某个非终极符A有如下的两个产生式：A→，A→(即有左公共前缀)消除方法：1.产生式形如：A1|2|…|n|表示不以开头的字符串。2.引进非终极符A’，使产生式替换为：AA|A1|2|…|n消除左递归一个文法含有下列形式的产生式时（1）AA|AVN,a,(VNVT)*（2）AB|BA|bA,BVN,a,,(VNVT)*其中（1）为直接左递归，（2）为间接左递归，因此文法中只要有A+A…，则称文法为左递归的。（1）对直接左递归形如：AA|消除左递归：AAAA|（2）间接左递归形如：AB|BA|b消除左递归：转为直接左递归形式：AA|b|或者BB||b按照直接左递归方式消除。去掉多余的产生式。有限自动机主要内容：确定有限自动机DFA(DeterninisticFA)非确定有限自动机NFA(NondeterninisticFA)NFA到DFA的转换DFA的化简确定有限自动机定义确定有限自动机DFA为一个五元组(,S,S0,f,Z)，其中：确定有限自动机是有穷字母表，每个元素称为一个输入字符；S是一个有穷集，它的每个元素称为一个状态；S0S是唯一的一个初始状态；f是在SS上的转换函数（单值）；ZSS，是终止状态集，又称为接受状态集；一个DFA的例子DFAM=({a,b},{S,U,V,Q},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确定有限自动机DFA的两种表示方式状态转换图结点表示状态，转换边表示转换函数，边的箭头方向指向转换函数中定义的转换方向。标识出初始状态和终止状态。状态转换矩阵可用二维数组描述。标识出初始状态和终止状态。若DFA中有f(SI,a)=SJ，则：Trans(SI，a)＝SJ确定有限自动机对于*中的任何字符串t,若存在一条从初始结点到某一终止结点的路径，且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFAM所接受（识别）。DFAM所能接受的字符串的全体记为L(M)称为M所能接受（识别）的语言。确定有限自动机DFA接受的字符串初始状态唯一。转换函数f:SS是一个单值函数，也就是说，对任何状态sS,和输入符号a,f(s,a)唯一地确定了下一个状态。即转换函数至多确定一个状态。没有空边。即没有输入为（）确定有限自动机DFA的确定性非确定有限自动机是字母表SS是状态集S0是初始状态集f是转换函数，但不要求是单值的f:SS(∪{})2SSTS是终止状态集非确定有限自动机及相关概念定义1：一个非确定有限自动机(NFA)A是一个五元组A=(,SS,S0,f,TS).其中非确定有限自动机定义2：设A是一个NFA，A=(,SS,S0,f,TS)则定义L(A)为从任意初始状态到任意终止状态所接受的字符串集合。L(A)={|s0s’,s0S0s’TS}NFA的一个例子SPZ00,1111自动机等价设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2)，则称A1和A2等价。NFA到DFA的转换（确定化）对于每一个非确定自动机A，存在一个确定自动机A’，使得L(A)=L(A’)。非确定有限自动机确定化算法—子集法已知NFA:A=(,S,f,S0,Z)构造DFA:A’=(,S’,f’,S0’,Z’)1.令A’的初始状态为S0’=[S1,S2,…Sk],其中S1…Sk是A的全部初始状态。2.若S’=[S1,…,Sm]是A’的一个状态，a则定义f’(S’,a)=f(S1,a)f(S2,a)…f(Sm,a)=Q将Q加入S’，重复该过程，直到S’收敛。3.若S’=[S1,…,Sn]是A’的一个状态,且存在一个Si是A