《有限自动机理论-2章形式语言教程文件》由会员分享，可在线阅读，更多相关《有限自动机理论-2章形式语言教程文件（325页珍藏版）》请在金锄头文库上搜索。
1、第二章 形式语言简介,形式语言和自动机理论中的语言是一个宽泛的概念。 一个字母表上的语言就是该字母表的某些字符串的集合。 语言中的字符串称为该语言的句子,语言的的定义可以从两个方面进行： ）从产生语言的角度； ）从接收(或识别)语言的角度。,产生语言 根据语言中的基本句子和其他句子的形成规则，得到(产生)该语言所包含的所有句子。 形式语言所研究的问题。,接收一个语言 使用某种自动机模型来接收字符串，该模型所接收的所有字符串，也形成一个语言。 自动机所研究的问题。,本章介绍形式语言的基本内容。,语言的形式定义,设是一个字母表， L*, L称为字母表上的一个语言, wL, w称为语言L的一个句子。
2、,2.1 例子语言,括号匹配串的语言。 该语言是指所有的左括号和右括号相匹配的串的集合； ( )，( )，( )( )等等都是该语言的句子 )( ，( )等等不是该语言的句子。,如何产生这个语言呢？ 即如何产生该语言所有句子呢？,实际上，就是需要给出语言中句子的构造（形成）规则。 递归方法提供了语言的良好的定义方式：语言中的句子的构造规律较明显 可以使用多种方法描述构造规则。,自然语言的描述方式，采用如下的 递归规则： ( )是该语言的最基本的句子； 若S是句子,则(S)是句子； 若S是句子,则SS是句子；,这些规则称为形成规则，根据这些规则，可以 产生该语言的任意的句子； 判断某个串是否是该
3、语言的句子- 语法分析。,例如,可以产生句子（） 而推断串 （） 不是句子。,规则(的个数)是有限的，但可以产生无限个句子、甚至长度无限的句子 因为规则是递归的。,BNF的描述方式,巴科斯和诺尔采用的巴科斯-诺尔范式(BNF-Backus-Naur Form)描述规则： := ( ) :=() :=,使用尖括号“”包括起来的部分，作为一个整体来看待，表示某个语法成分 需要使用字母表中的字母来定义其构成 符号“:=”是BNF本身的符号（元符号），代表“定义为”或“是”。 符号“( ”和“ )”是字母表的元素。,Chomsky采用的符号化(形式化)的描述方式，运用规则（称为产生式）： S( ) S
4、(S) SSS,“”代表“定义为”或者“是” ， 它的左边和右边分别称为该产生式的左边和右边,根据产生式,可以生成任意句子； 可以判断一个串是否为句子,产生句子的过程,从S开始，可以反复利用产生式的右边代替产生式的左边（推导过程）， 最终可以产生括号匹配的的句子。,例:句子( )( )( )的推导过程,S =SS =(S)S =( )S =( )(S) =( )(SS) =( )( )S) = ( )( )( ),产生式的个数是有限的，规则是递归的，所有的小括号匹配的串，都可以由产生式产生； 它们组成的集合就称为一个语言。,S称为非终结符，在推导过程中，可以被代替的符号。 (和)称为终结符，在
5、推导过程中，不可以被代替的符号。 是产生式系统的元符号，不属于非终结符，也不属于非终结符。,例2-1：由偶数个0组成的串的语言。 规则的自然语言描述方式： 00是该语言的基本的句子； 若S是句子,则00S是句子。,形式化的描述方式： S00 S00S,问题：,将产生式S00S换成 S0S0或SS00或SSS 是否还产生相同的语言？,结论：,一个语言，可以使用不同的产生式组合来产生。,考虑,由奇数个1组成串的语言（产生规则）,例2-2,高级程序设计语言中的算术表达式(的语言)的产生。,自然语言的描述方式,单个变量是最基本的句子； 若E是一个句子，则EAE是一个句子（其中A代表运算符+、-、*、/
6、） 若E是一个句子，则(E)是句子；,形式语言的描述方式, E i （i代表单个变量） EEAE E(E) A+ A- A* A/,思考：,字母表为？ 若以A开始推导，则产生？,其中 ： A+，A-，A*，A/ 四个产生式的左边是相同的符号，可以合并为 A+|-|*|/ +、-、*、/ 称为A的侯选式。,E i EEAE E(E) 也可以记为： E i|EAE|(E),注意：,这组产生式 没有表示出运算符的优先级。,表示出运算符的优先级的产生式： EE+T|E-T|T TT*F|T/F|F F(E)|i,其中： E代表表达式，T代表项，F代表因子 (E)代表的是带小括号的表达式 表示：先因子，
7、再*、/，最后+、-,如果使用%代表模运算(即取余数运算)、使用代表指数运算，则有 EE+T|E-T|T TT*F|T/F|T%F|A AFA|F F(E)|i,注意,需要考虑运算的结合性： 是右结合的。,例2-3,标识符(以字母开头的字母、数字的串)的产生(仅考虑小写字母)。,从标识符的形成角度考虑,IL IIL IID La|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t u|v|w|x|y|z D0|1|2|3|4|5|6|7|8|9,思考：,上例是从标识符的形成角度思考问题。 从标识符的定义角度考虑，则？,注意,D0|1|2|3|4|5|6|7|8|9 不能
8、简写为 D0|9,将I的定义加入到表达式中：,EE+T|E-T|T TT*F |T/F|F F (E)|I IL|IL|ID L D,思考:,其他类型的表达式（如关系表达式等）的定义：、=、= 标识符(以下划线或字母开头的字母、下划线和数字的串)的产生。,例2-4,C语言中简单变量的说明语句的定义。 C语言中的说明语句形式为： TYPE 变量名表； TYPE 变量名表； TYPE 变量名表；,产生式为：,SSS|P PT V； Tint|char|float|double| VV,V|I,用户定义类型,IL|IL|ID L D,思考,PASCAL语言的简单变量的说明语句的形成。 VAR 变量名
9、表: TYPE; 变量名表: TYPE ; 变量名表: TYPE;,2.2 文法和语言的关系,语言的定义 文法的定义 文法与语言的关系,对于语言，在字母表上，按照一定的构成规则，根据语言句子的结构特点，可以定义一个产生该语言的文法。 使用文法作为语言的有穷描述，不仅可以描述出语言的结构特征，而且可以产生这个语言的所有句子。,定义2-1 短语结构文法(文法)的定义,文法G是一个四元式， G=(，V，S，P) 是有限字符的集合(字母表)， 元素称为字母或者终结符； V是有限字符的集合-非终结符集合，元素称为变量或者非终结符；,短语结构文法(文法)的定义,SV，称为文法的开始符号； P是有序偶对(，
10、)的集合：是集合(V)上的字符串，至少包含一个非终结符；是集合(V)*的元素 一般，将有序偶对(，)记为 称为产生式；,如果有，称之为空串产生式或者产生式。 如果有AB，称之为单产生式。,一个产生式的左边可能不只一个符号； 第一个产生式的左边只能有一个符号，就是开始符号S。,文法的作用就是产生一个语言。,约定：如果没有特别说明,则,第一个产生式左边的符号，就是开始符号，可以不为S； 大写的英文字母代表非终结符； 小写的英文字母a，b，c，d，e和数字代表终结符；,约定：如果没有特别说明,则,小写的英文字母u，v，w，x，y，z代表终结符串； 小写的希腊字母，、 代表非终结符和终结符串；,推导（
11、派生）的定义2-2,文法G，和是集合(V)上的串 = pvr ，=pur(p和r可能同时为) 而vu是文法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 表示
12、y可以经过任意步推导出z，即 y=z；或者 y=+z,思考：,对于任意文法G： S=*S S=+S 一定都成立吗？,句型和句子,对于文法G，如果S=*，则称是文法的一个句型 进一步 ，若 *, 称为句子,定义2-3 语言的定义,给定文法G，有开始符号S 把S可以推导出的所有句子的集合 称为由文法产生的语言，记为L(G) L(G)=|S=*，且*,例,文法 G= (,),S,S, S( ), S(S), SSS ) 产生语言 L(G)=w|w是括号匹配的串,注意:,文法G产生语言L，必须满足： G推导产生的所有句子都在L中 L的任意句子都可以由G推导产生,对于文法G=(，V，S，P) 约定： 第
13、一个产生式左边的符号，就是开始符号（可以不是S）； 大写的英文字母代表非终结符。,对于文法（G），只需给出该文法的所有产生式即可。 产生括号匹配语言的文法可以写成 S( ) S(S) SSS,还可以再简写成 S( )|(S)|SS,文法和语言的3类问题,已知文法 得到该文法产生的语言 已知语言 构造产生该语言的某个文法 判断一个语言是否由某一个文法产生,第一类问题,文法 SaSa|bSb|c 产生的语言是什么？ 需要考虑所有产生式的所有可能使用情况（包括顺序和次数）,第二类问题,构造产生语言L的文法。 L= wwT|wa,b,c+ 其中：wT是w的逆（反序）,思考：,产生下列语言的文法： L1
14、=anbn|n0 L2=anbn|n0,第三类问题,文法 S0B|1A A0|0S|1AA B1|1S|0BB 产生的语言是否为L：,L=|0,1+， 且中有相同多的0和1？,第三类问题还包括,判断一个语言是否由某个文法产生。 证明一个语言由某一个文法产生。,注意：,一个语言可以由多个不同的文法产生。 一个文法只能产生一个语言。,例2-5,G1：S0|1|00|11 G2：SA|B|AA|BB A0 B1 L(G1)=L(G2)=0,1,00,11,文法等价,如果文法G1和文法G2产生同一个语言，则称文法G1和G2是等价的文法。 L(G1)= L(G2),注意区别：,文法G1和G2等价 文法G
15、1和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型文法产生式的标准形式,yAzyz 其中：AV； y,z(V)* (V)+,1型文法,可以证明： 任意的1型文法，都可以改造为
16、1型文法的标准形式。,2型文法,如果对于任意P，均有|且V成立，则称G为2型文法，或上下文无关文法(CFG) 对应的L(G)称为2型语言或者上下文无关语言(CFL)。,3型文法,如果对于任意P，具有形式 Aw，AwB 其中，A，BV，w+ 则称G为3型文法，或右线性文法 RLG，也可称为正则文法RG。,对应的L(G)称为3型语言 或 右线性语言RLL或 正则语言RL。,四类文法和对应的四类语言之间是真包含关系。,思考,如果文法G有产生式，则G是 型文法?,文法分类判断方法：,文法G=(，V，S，P)，则 1) G是短语结构文法； 2) 如果文法G的所有产生式的左边长度小于等于右边长度部分，那么G是上下文相关文法；,3) 如果上下文相关文法G的所有
