2019有限自动机理论CH.ppt

第二章形式语言简介形式语言和自动机理论中的语言是一个广泛的概念。一个字母表上的语言就是该字母表的某些字符串的集合。语言中的字符串称为该语言的句子语言的的定义可以从两个方面进行：１）从产生语言的角度；２）从接收(或识别)语言的角度。产生一个语言，目的就是根据语言中的基本句子和句子的形成规则，得到(产生)该语言所包含的所有句子。这是形式语言所研究的问题。接收一个语言，目的就是使用某种自动机模型来接收句子，该模型所接收的所有句子，也形成一个语言。这是自动机所研究的问题。本章介绍形式语言的基本内容。语言的形式定义设是一个字母表，L*,L称为字母表上的一个语言,wL,w称为语言L的一个句子。2.1例子语言括号匹配串的语言。该语言是指所有的左括号和右括号相匹配的串的集合；()，(())，()()等等都是该语言的句子)(，())等等不是该语言的句子。如何产生这个语言呢？即如何产生该语言所有句子呢？实际上，就是需要给出语言中句子的构造（形成）规则。递归定义提供了语言的良好的定义方式，使得语言中的句子的构造规律较明显。可以使用多种方法描述构造规则。自然语言的描述方式，采用如下的递归规则：①()是该语言的最基本的句子；②若S是句子,则(S)是句子；③若S是句子,则SS是句子；这些规则称为形成规则，根据这些规则，可以(1)产生该语言的任意的句子；(2)判断某个串是否是该语言的句子。例如可以产生句子（（））而推断串（（）））不是句子。规则(的个数)是有限的，但可以产生无限个句子和长度无限的句子；因为规则是递归的。BNF的描述方式巴科斯和诺尔采用的巴科斯-诺尔范式（BNF--Backus-NaurForm）描述规则：括号匹配串::=()括号匹配串::=(括号匹配串)括号匹配串::=括号匹配串括号匹配串使用尖括号“”和“”包括起来的部分，作为一个整体来看待，表示某个语法成分需要使用字母表中的字母来定义其构成符号“::=”是BNF本身的符号（元符号），代表“定义为”或“是”。符号“(”和“)”是字母表的元素。Chomsky采用的符号化(形式化)的描述方式，运用如下的规则（这些规则被称为产生式）：①S→()②S→(S)③S→SS“→”代表“定义为”或者“是”，它的左边和右边分别称为该产生式的左边和右边根据产生式可以生成任意句子；可以判断一个串是否为句子(语法分析)产生句子的过程从S开始，利用产生式的右边代替产生式的左边（称之为推导过程）进行多次推导，可以得到括号匹配的的句子。例:句子(())(()())的推导过程S=SS=(S)S=(())S=(())(S)=(())(SS)=(())(()S)=(())(()())产生式的个数是有限的，规则是递归的，因而所有的小括号匹配的串，都可以由产生式产生；它们组成的集合就称为一个语言。S称为非终结符，在推导过程中，可以被代替的符号。(和)称为终结符，在推导过程中，不可以被代替的符号。→是产生式系统的元符号，不属于非终结符，也不属于非终结符。例2-1：由偶数个0组成的串的语言。规则的自然语言描述方式：①00是该语言的基本的句子；②若S是句子,则00S是句子。形式化的描述方式：S→00S→00S问题：将产生式S→SS换成S→0S0或S→S00或S→SS是否还产生相同的语言？结论：一个语言，可以使用不同的产生式组合来产生。考虑由奇数个1组成串的语言（产生规则）例2-2高级程序设计语言中的算术表达式(的语言)的产生。自然语言的描述方式①单个变量是最基本的句子；②若E是一个句子，则EAE是一个句子（其中A代表运算符+、-、*、/）③若E是一个句子，则(E)是句子；形式语言的描述方式①E→i（i代表单个变量）②E→EAE③E→(E)④A→+⑤A→-⑥A→*⑦A→/思考：字母表为？若以A开始推导，则产生？其中：A→+，A→-，A→*，A→/四个产生式的左边是相同的符号，可以合并为A→+|-|*|/+、-、*、/称为A的侯选式。E→iE→EAEE→(E)也可以记为：E→i|EAE|(E)注意：这组产生式没有表示出运算符的优先级。表示出运算符的优先级的产生式：E→E+T|E-T|TT→T*F|T/F|FF→(E)|i其中：E代表表达式，T代表项，F代表因子(E)代表的是带小括号的表达式。表示：先算因子，再*、/，最后+、-。如果使用%代表模运算(即取余数运算)、使用^代表指数运算，则有E→E+T|E-T|TT→T*F|T/F|T%F|AA→F^A|FF→(E)|i注意需要考虑^运算的结合性：^是右结合的。例2-3标识符(以字母开头的字母、数字的串)的产生(仅考虑小写字母)。从标识符的形成角度考虑I→LI→ILI→IDL→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|tu|v|w|x|y|zD→0|1|2|3|4|5|6|7|8|9思考：上例是从标识符的形成角度思考问题。从标识符的定义角度考虑，则？注意D→0|1|2|3|4|5|6|7|8|9不能简写为D→0|…|9将I的定义加入到表达式中：E→E+T|E-T|TT→T*F|T/F|FF→(E)|II→L|IL|IDL→…D→…思考:其他类型的表达式（如关系表达式等）的定义：、=、、=、、=标识符(以下划线或字母开头的字母、下划线和数字的串)的产生。例2-4C语言中简单变量的说明语句的定义。C语言中的说明语句形式为：TYPE变量名表；TYPE变量名表；…TYPE变量名表；产生式为：S→SS|PP→TV；T→int|char|floatV→V,V|II→L|IL|IDL→…D→…思考PASCAL语言的简单变量的说明语句的形成。VAR变量名表:TYPE;变量名表:TYPE;…变量名表:TYPE;2.2文法和语言的关系语言的定义文法的定义文法与语言的关系再次强调：语言就是字母表上的字符串组成的一个集合。语言中的字符串称为句子。文法的作用就是产生一个语言。有穷语言的表示较容易。即使语言中的句子的组成没有什么规律，也可以使用枚举的方式列出语言中的所有句子。对于无穷语言，需要使用有穷描述的方式表达。需要从语言的句子的一般构成规律去考虑问题。从语言的有穷描述来表达语言的方法对大多数语言是有效的。在（使用计算机）判断一个字符串是否是某个语言的句子时(语法分析)从句子和语言的结构特征上着手是非常重要的。对于语言，可以在字母表上，按照一定的构成规则，根据语言的结构特点，可以定义一个产生该语言的文法。使用文法作为相应语言的有穷描述，不仅可以描述出语言的结构特征，而且可以产生这个语言的所有句子。定义2-1短语结构文法(文法)的定义文法G是一个四元式，G=(∑，V，S，P)∑是一个有限字符的集合(字母表)，它的元素称为字母或者终结符；V是一个有限字符的集合--非终结符集合，它的元素称为变量或者非终结符；短语结构文法(文法)的定义S∈V，称为文法的开始符号；P是有序偶对(α，β)的集合，其中α是集合(∑UV)上的字符串，但至少包含一个非终结符；β是集合(∑UV)*的元素。一般，将有序偶对(α，β)记为α→β，称为产生式；如果有α→ε，称之为空串产生式或者ε产生式。如果有A→B，称之为单产生式。一个产生式的左边可能不只一个符号；第一个产生式的左边只能有一个符号，就是开始符号S。文法的作用就是产生一个语言。约定：如果没有特别说明,则第一个产生式左边的符号，就是开始符号，可以不为S；大写的英文字母代表非终结符；小写的英文字母a，b，c，d，e和数字代表终结符；小写的英文字母u，v，w，x，y，z代表终结符串；小写的希腊字母α，β代表非终结符和终结符串；推导（派生）的定义2-2文法G，α和β是集合(∑UV)上的串α=pvr，β=pur(p和r可能同时为ε)而v→u是文法G的一个产生式,则称α可以直接推导出β，记为α=β，既pvr=pur。推导的实质产生式的右边替换产生式的左边非终结符代表在推导的过程中可以被替代的符号，终结符代表在推导的过程中不可以被替代的符号。推导的逆过程称为归约。与pvr=pur对应，称串pur可以直接归约成串pvr记为pvr=pur多步推导（至少一步）y=+z表示y可以经过多步推导出z，即存在串的序列1，2，3，…，n；有y=1，z=n，且i=i+1；对所有ni≥1。任意步推导(包括0步)y=*z表示y可以经过任意步推导出z，即①y=z；或者②y=+z。思考：对于任意文法G：S=*SS=+S一定都成立吗？最左推导和最右推导如果在推导的过程中，每一步都是将推导产生的串的最左边的非终结符代替掉--最左推导如果每一步都是将推导产生的串的最右边的非终结符代替掉--最右推导(规范推导)，当然，还有其它方式的推导过程（例如混合）而最左推导和最右推导是比较常用的推导方式。句型和句子对于文法G，如果S=*ω，则称ω是文法的一个句型，若ω∈*,ω称为句子。定义2-3语言的定义给定文法G，有开始符号S，则把S可以推导出所有句子的集合，称为由文法产生的语言，记为L(G)，即L(G)={ω|S=*ω，且ω∈∑*}例文法G=({(,)},{S},S,{S→(),S→(S),S→SS})产生语言L(G)={w|w是括号匹配的串}注意:文法G产生语言L，必须：①G推导产生的所有句子都在L中②L的任意一个句子都可以由G产生对于文法G=(∑，V，S，P)约定：第一个产生式左边的符号，就是开始符号（可以不是S）；大写的英文字母代表非终结符。对于文法（G），只需给出该文法的所有产生式即可。产生括号匹配语言的文法可以写成S→()S→(S)S→SS还可以再简单写成S→()|(S)|SS文法和语言的3类问题已知文法,得到该文法产生的语言已知语言,构造产生该语言的某个文法判断一个语言是否由某一个文法产生关系1：文法S→aSa|bSb|c|ε产生的语言是什么？S能够产生的所有句子，需要考虑3个产生式所有可能使用情况注意对称性关系2：构造产生语言L的文法。L={wwT|w∈{a,b,c}+}其中：wT是w的逆（反序）思考：产生下列语言的文法：L1={anbn|n0}L2={anbn|n≧0}关系3：文法S→0B|1AA→0|0S|1AAB→1|1S|0BB是否产生的语言L：L={ω|ω∈{0,1}+，且ω中有相同多的0和1}？注意：一个语言可以由多个不同的文法产生。一个文法只能产生一个语言。例2-5G1：S→0|1|00|11G2：S→A|B|AA|BBA→0B→1L(G1)=L(G2)={0,1,00,11}文法等价如果文法G1和文法G2产生同一个语言，则称文法G1和G2是等价的文法。L(G1)=L(G2)注意区别：文法G1和G2等价文法G1和G2相同。2.3Chomsky对文法的分类Chomsky对文法进行了分类；对语言的分类，是根据产生语言的文法的分类进行的0型文法对于一般的短语结构文法(PSG)G=(∑，V，S，P)G称为0型文法，对应的L(G)称为0型语言或者短语结构语言(PSL)、递归可枚举集。1型文法如果对于任意∈P，均有||≤||成立，则称G为1型文法，或上下文相关文法(CSG)。对应的L(G)称为1型语言或者上下文相关语言(CSL)。1型文法1型文法产生式的标准形式为：yAz→yωz其中：A∈V；y,z∈(∑∪V)*，ω∈(∑∪V)+；1型文法可以证明，任意的1型文法，都可以改造为1型文法的标准形式。2型文法如果对于任意∈P，均有||≤||且∈V成立，则称G为2型文法，或上下文无关文法(CFG)对应的L(G)称为2型语言或者上下文无关语言(CFL)。3型文法如果对于任意∈P，具有形式Aw，AwB其中，A，B∈V，w∈∑+则称G为3型文法，或右线性文法RLG，也可称为正则文法RG。对应的L(G)称为3型语言或右线性语言RLL或正则语言RL。四类文法和对应的四类语言之间是真包含关系。思