有限自动机理论-2章形式语言.ppt
《有限自动机理论-2章形式语言.ppt》由会员分享,可在线阅读,更多相关《有限自动机理论-2章形式语言.ppt(325页珍藏版)》请在三一文库上搜索。
1、第二章 形式语言简介,形式语言和自动机理论中的语言是一个宽泛的概念。 一个字母表上的语言就是该字母表的某些字符串的集合。 语言中的字符串称为该语言的句子,语言的的定义可以从两个方面进行: )从产生语言的角度; )从接收(或识别)语言的角度。,产生语言 根据语言中的基本句子和其他句子的形成规则,得到(产生)该语言所包含的所有句子。 形式语言所研究的问题。,接收一个语言 使用某种自动机模型来接收字符串,该模型所接收的所有字符串,也形成一个语言。 自动机所研究的问题。,统一的理论,形式语言与自动机作为统一的理论,实际上包括3个方面的内容: 1) 形式语言理论(产生语言) 2) 自动机理论(接收语言)
2、 3) 形式语言与自动机的等价性理论,本章介绍形式语言的基本内容。,语言的形式定义,设是一个字母表, L*, L称为字母表上的一个语言, wL, w称为语言L的一个句子。,2.1 例子语言,括号匹配串的语言。 该语言是指所有的左括号和右括号相匹配的串的集合; ( ),( ),( )( )等等都是该语言的句子 )( ,( )等等不是该语言的句子。,如何产生这个语言呢? 即如何产生该语言所有句子呢?,实际上,就是需要给出语言中句子的构造(形成)规则。 递归方法提供了语言的良好的定义方式:语言中的句子的构造规律较明显 可以使用多种方法描述构造规则。,自然语言的描述方式,采用如下的 递归规则: ( )
3、是该语言的最基本的句子; 若S是句子,则(S)是句子; 若S是句子,则SS是句子;,这些规则称为形成规则,根据这些规则,可以 产生该语言的任意的句子; 判断某个串是否是该语言的句子- 语法分析。,例如,可以产生句子() 而推断串 () 不是句子。,规则(的个数)是有限的,但可以产生无限个句子、甚至长度无限的句子 因为规则是递归的。,BNF的描述方式,巴科斯和诺尔采用的巴科斯-诺尔范式(BNF-Backus-Naur Form)描述规则: := ( ) :=() :=,使用尖括号“”包括起来的部分,作为一个整体来看待,表示某个语法成分 需要使用字母表中的字母来定义其构成 符号“:=”是BNF本身
4、的符号(元符号),代表“定义为”或“是”。 符号“( ”和“ )”是字母表的元素。,Chomsky采用的符号化(形式化)的描述方式,运用规则(称为产生式): S( ) S(S) SSS,“”代表“定义为”或者“是” , 它的左边和右边分别称为该产生式的左边和右边,根据产生式,可以生成任意句子; 可以判断一个串是否为句子,产生句子的过程,从S开始,可以反复利用产生式的右边代替产生式的左边(推导过程), 最终可以产生括号匹配的的句子。,例:句子( )( )( )的推导过程,S =SS =(S)S =( )S =( )(S) =( )(SS) =( )( )S) = ( )( )( ),产生式的个数
5、是有限的,规则是递归的,所有的小括号匹配的串,都可以由产生式产生; 它们组成的集合就称为一个语言。,S称为非终结符,在推导过程中,可以被代替的符号。 (和)称为终结符,在推导过程中,不可以被代替的符号。 是产生式系统的元符号,不属于非终结符,也不属于非终结符。,例2-1:由偶数个0组成的串的语言。 规则的自然语言描述方式: 00是该语言的基本的句子; 若S是句子,则00S是句子。,形式化的描述方式: S00 S00S,问题:,将产生式S00S换成 S0S0或SS00或SSS 是否还产生相同的语言?,结论:,一个语言,可以使用不同的产生式组合来产生。,考虑,由奇数个1组成串的语言(产生规则),例
6、2-2,高级程序设计语言中的算术表达式(的语言)的产生。,自然语言的描述方式,单个变量是最基本的句子; 若E是一个句子,则EAE是一个句子(其中A代表运算符+、-、*、/) 若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),注意:,这组产生式 没有表示出运算符的优先级。,表示出运算
7、符的优先级的产生式: EE+T|E-T|T TT*F|T/F|F F(E)|i,其中: E代表表达式,T代表项,F代表因子 (E)代表的是带小括号的表达式 表示:先因子,再*、/,最后+、-,如果使用%代表模运算(即取余数运算)、使用代表指数运算,则有 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
8、 D0|1|2|3|4|5|6|7|8|9,思考:,上例是从标识符的形成角度思考问题。 从标识符的定义角度考虑,则?,注意,D0|1|2|3|4|5|6|7|8|9 不能简写为 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;
9、 Tint|char|float|double| VV,V|I,用户定义类型,IL|IL|ID L D,思考,PASCAL语言的简单变量的说明语句的形成。 VAR 变量名表: TYPE; 变量名表: TYPE ; 变量名表: TYPE;,2.2 文法和语言的关系,语言的定义 文法的定义 文法与语言的关系,对于语言,在字母表上,按照一定的构成规则,根据语言句子的结构特点,可以定义一个产生该语言的文法。 使用文法作为语言的有穷描述,不仅可以描述出语言的结构特征,而且可以产生这个语言的所有句子。,定义2-1 短语结构文法(文法)的定义,文法G是一个四元式, G=(,V,S,P) 是有限字符的集合(字
10、母表), 元素称为字母或者终结符; V是有限字符的集合-非终结符集合,元素称为变量或者非终结符;,短语结构文法(文法)的定义,SV,称为文法的开始符号; P是有序偶对(,)的集合:是集合(V)上的字符串,至少包含一个非终结符;是集合(V)*的元素 一般,将有序偶对(,)记为 称为产生式;,如果有,称之为空串产生式或者产生式。 如果有AB,称之为单产生式。,一个产生式的左边可能不只一个符号; 第一个产生式的左边只能有一个符号,就是开始符号S。,文法的作用就是产生一个语言。,约定:如果没有特别说明,则,第一个产生式左边的符号,就是开始符号,可以不为S; 大写的英文字母代表非终结符; 小写的英文字母
11、a,b,c,d,e和数字代表终结符;,约定:如果没有特别说明,则,小写的英文字母u,v,w,x,y,z代表终结符串; 小写的希腊字母,、 代表非终结符和终结符串;,推导(派生)的定义2-2,文法G,和是集合(V)上的串 = pvr ,=pur(p和r可能同时为) 而vu是文法G的一个产生式, 则称直接推导出 记为= ,即 pvr =pur,推导的实质 产生式的右边替换产生式的左边,非终结符代表在推导的过程中可以被替代的符号, 终结符代表在推导的过程中不可以被替代的符号。,推导的逆过程称为归约。 与pvr =pur对应,串pur可以直接归约成串pvr 记为pvr =pur,多步推导(至少一步),
12、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=*S S=+S 一定都成立吗?,句型和句子,对于文法G,如果S=*,则称是文法的一个句型 进一步 ,若 *, 称为句子,定义2-3 语言的定义,给定文法G,有开始符号S 把S可以推导出的所有句子的集合 称为由文法产生的语言,记为L(G) L(G)=|S=*,且*,例,文法 G= (,),S,S, S( ), S(S), SSS ) 产生语言 L
13、(G)=w|w是括号匹配的串,注意:,文法G产生语言L,必须满足: G推导产生的所有句子都在L中 L的任意句子都可以由G推导产生,对于文法G=(,V,S,P) 约定: 第一个产生式左边的符号,就是开始符号(可以不是S); 大写的英文字母代表非终结符。,对于文法(G),只需给出该文法的所有产生式即可。 产生括号匹配语言的文法可以写成 S( ) S(S) SSS,还可以再简写成 S( )|(S)|SS,文法和语言的3类问题,已知文法 得到该文法产生的语言 已知语言 构造产生该语言的某个文法 判断一个语言是否由某一个文法产生,第一类问题,文法 SaSa|bSb|c 产生的语言是什么? 需要考虑所有产
14、生式的所有可能使用情况(包括顺序和次数),第二类问题,构造产生语言L的文法。 L= wwT|wa,b,c+ 其中:wT是w的逆(反序),思考:,产生下列语言的文法: L1=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
15、)=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)称
16、为1型语言或者上下文相关语言(CSL)。,1型文法产生式的标准形式,yAzyz 其中:AV; y,z(V)* (V)+,1型文法,可以证明: 任意的1型文法,都可以改造为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。,四类文法和对应的四类语言之间是真包含关系。,思考,如果文法
17、G有产生式,则G是 型文法?,文法分类判断方法:,文法G=(,V,S,P),则 1) G是短语结构文法; 2) 如果文法G的所有产生式的左边长度小于等于右边长度部分,那么G是上下文相关文法;,3) 如果上下文相关文法G的所有产生式的左边都是一个非终结符, 那么G是上下文无关文法;,4) 如果上下文无关文法G的所有产生式右边最多只有一个非终结符 且该非终结符号只能出现在最右边,那么G是正则文法。,文法G: S01|101S 是RG,CFG,CSG和PSG,文法G: SAaS|AS Aa|b|c|d 是CFG,CSG和PSG,但不是RG。,文法G SaB aBab 是CSG和PSG,但不是CFG和
18、RG。,文法G S aB aBab aBa 是PSG,但不是CFG、RG和CSG。,形如的产生式称为空产生式,也可称为产生式。 CSG、CFG和RG,都不能含有空产生式,所以任何CSL、CFL和RL中都不包含(空句子)。,如果允许在CSG、CFG和RG中含有空产生式, 也就允许CSL、CFL和RL中包含空句子。,如果语言L没有空句子,则 文法中增加产生式 S 就可以直接产生空句子。,文法扩充分类:,设文法G=(,V,S,P) 如果S不出现在任何产生式的右部,则,(1) 若G是CSG G=(,V,S,PS) 仍然为CSG; L(G) 是CSL。,(1) 若G是CFG G=(,V,S,PS) 仍然
19、为CFG; L(G) 是CFL。,(1) 若G是RG G=(,V,S,PS) 仍然为RG; L(G) 是RL。,思考,为什么要有条件 S不出现在任何产生式的右部?,设正则文法RG:Sab|aS,则 L(G)=a+b G:Sab|aS| L(G)=a+b, , a+ 增加了空句子,但多产生句子a+,定理2-1,文法G=(,V,S,P) , 存在与G同类型的文法 G=(,V, S P) ,使得 L(G)=L(G) 且S不出现在G的任何产生式右部,证明:,先根据G构造满足条件的G,然后证明两者等价。 构造G=(,VS,S,P) 其中P=PS|SP G与G有相同的类型。,G与G等价,即证明L(G)=L
20、(G) 需要证明 L(G) L(G) L(G) L(G) ,特殊情况,如果S不出现在P中任何产生式的右边,则 G=G,思考,文法的S不出现在产生式的右部 那么,S的作用是什么? 仅仅负责推导的开始; 不能够作为一般非终结符使用,下列命题成立,有语言L,设置L = L (1)若L是CSL,则L仍然是CSL。 (2)若L是CFL,则L仍然是CFL。 (3)若L是RL,则L仍然是RL。,证明:,证明第(1)个命题, (2)(3)同理可证。,证明,设L是CSL,则存在一个 CSG=(,V,S,P) 使得 L(G)=L。,设S不出现在G的产生式右部。 构造 G=(,V,S,PS) G也是CSG。,S不出
21、现在G中产生式的右部 增加的S,不可能被使用到任何非空句子的推导中,则 L(G)=L(G) L(G)是CSL。,结论,增加空句子不影响语言的类型。,同理,删除空句子也不影响语言的类型。,下列命题成立,有语言L,L = L- (1)若L是CSL,则L仍然是CSL。 (2)若L是CFL,则L仍然是CFL。 (3)若L是RL,则L仍然是RL。,证明:,证明第(1)个命题, (2)(3)同理可证。,证明,设L是CSL,则存在一个 CSG=(,V,S,P) 使得 L(G)=L。,如果 L,L-=L L- 是CSL。,如果L,设S不出现在G的产生式的右部。 构造=(,V,S,P-S), G也是CSG。,S
22、不出现在G产生式的右部 去掉S,则不影响任何非空句子的推导, L(G)=L(G)-。 L(G)是CSL。,除了生成空句子外,空产生式可以不用于其他句子的推导中。 空句子在一个语言中的存在并不影响该语言的有穷描述。,文法可以包含一般的空串产生式, 属于0型文法。,L(G)=w|w0,1+,且w以0开始 G可以为: S0|0A A0|1|0A|1A 其中: A产生0,1+,或,S? A|0A|1A 其中:A产生0,1*,2.4文法产生语言,例 文法 S0S S0 产生语言L=0n|n0,分析,如果开始使用第2个产生式S0,则S=0,就不能再往下进行推导了。 产生基本句子0;,若使用产生式S0S,n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 有限 自动机 理论 形式语言
链接地址:https://www.31doc.com/p-3297691.html