形式语言与自动机语言及文法.ppt

《形式语言与自动机语言及文法.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机语言及文法.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、形式语言与自动机课件语言及文法现在学习的是第1页，共33页第一节第一节 语言的定义与运算语言的定义与运算一、一、语言的一些术语：语言的一些术语：n 字母表：字母表：字符的有限集合，记为字符的有限集合，记为T。n字符串：字符串：由字母表由字母表T中的字符构成的序列称中的字符构成的序列称字母表字母表T上的字符串（句子）。上的字符串（句子）。n 常记为常记为u,v,w,x,y,z；n 常用常用a,b,c,d 标识单个字符。标识单个字符。现在学习的是第2页，共33页字 母 表（Alphabet）n 概念 形式符号的集合n n 记号 常用 T、表示n n 举例n 英文字母表英文字母表 a,b,z,A,B

2、,Z n 英文标点符号表英文标点符号表 ,;:.?!“”()n 汉字表汉字表 ,自自,动动,机机,n 化学元素表化学元素表 H,He,Li,n T=a,n,y,任任,意意 现在学习的是第3页，共33页字 符 串（string）n 概念 字母表 T 上的一个字符串（简称串），或称为n 字（word），为 T 中字符构成的一个有限序列。空串（empty string）,用 表示，不包含任何 字符。n 举例 设 T=a,b，则,a,ba,bbaba 等都是串n n 字符串 w 的长度，记为 w，是包含在 w 中字符的个数n 举例 =0，bbaba=5 ai 表示含有表示含有i个个a的字符串的字符串现

3、在学习的是第4页，共33页n 连接（concatenation）n设 x,y为串,且 x a1a2 am,y b1b2 bn,n则 x 与 y 的连接n x y a1a2 am b1b2 bnn 连接运算的性质 n (x y)z x（y z）n x x x n x y x+y n 关 于 字 符 串 的 运 算现在学习的是第5页，共33页n 其它 如 取头字符，取尾部，子串匹配 等n 设设1,2,3是字母表是字母表T上的字符串，称上的字符串，称1是字符串是字符串12的前缀，的前缀，2是字符串是字符串12的后缀，且的后缀，且2是字符是字符串串123的子串。的子串。n 空串是任何字符串的前缀，后缀

4、及子串。空串是任何字符串的前缀，后缀及子串。n 例例：abc的前缀的前缀 a ab abc.后缀后缀 c bc abc.子串子串 a b c ab bc abc ,即一个字符串可以看作是多个字符串的连接。即一个字符串可以看作是多个字符串的连接。n 关 于 字 符 串 的 运 算现在学习的是第6页，共33页n 字符串的逆用 表示。是字符串的倒置。=b1b2bn =bnbn-1b2b1n 空串的逆还是现在学习的是第7页，共33页字 母 表 的 幂 运 算n 幂运算 设 T 为字母表，n 为任意自然数，n 定义（1）T0=n （2）设 x Tn-1，a T，则a x Tnn （3）Tn 中的元素只能

5、由（1）和（2）生成n n 闭包 T*=T0 T1 T2 n n 闭包 T+=T1 T2 T3 n n T*=T+，T+=T*现在学习的是第8页，共33页闭包的物理意义n T的星号闭包T*：字母表T上的所有字符串和空串的集合。n T的正闭包T+：字母表T上的所有字符串构成的集合。T*=T+n举例 设 T=0，1，则n T0=，T1=0，1，n T2=00，01，10，11，n T*=，0，1，00，01，10，11，n T+=0，1，00，01，10，11，现在学习的是第9页，共33页语 言（Languages）n 概念 设 T 为字母表，则任何集合 L T*是字母表T上的一个语言（langu

6、age）n n 举例n n 英文单词集英文单词集 ,English,words,n C 语言程序集语言程序集 字母表？字母表？n 汉语成语集汉语成语集 ,马到成功马到成功,n 化学分子式集化学分子式集 ,H2O,NaCl,n any,任意任意 现在学习的是第10页，共33页语 言（Languages）n举例：设T=a，b 则则 L1 =anbn|n1 L3=bk|k 是质数是质数 L2 =只有一个空句子的语言只有一个空句子的语言 L4=空语言空语言 均为字母表均为字母表T上的语言。上的语言。n由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。现在学习的是第11页

7、，共33页语言的基本运算n 语言的积：两个语言L1 和L2的积L1 L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。设T=a,b，L1和 L2是T上的语言。L1=ab,ba L2=aa,bb则 L1 L2=abaa,abbb,baaa,babb L2 L1=aaab,aaba,bbab,bbban L1 L2 L2 L1 语言的积不可交换。现在学习的是第12页，共33页语言的基本运算n 语言的幂：语言的幂可归纳定义如下语言的幂可归纳定义如下:L0=Ln=L Ln-1=Ln-1 L n 1上例中，上例中，L12=abab,abba,ba

8、ab,baba L22=aaaa,aabb,bbaa,bbbb 现在学习的是第13页，共33页第二节 文法n定义：所谓文法是用来定义语言的一个数学模型：所谓文法是用来定义语言的一个数学模型n表示语言的方法：n若语言若语言L是有限集合，可用是有限集合，可用列举法n若若L是无限集合（集合中的每个元素有限长度），是无限集合（集合中的每个元素有限长度），用其他方法。用其他方法。n方法一：文法产生系统，由定义的文法规则产生方法一：文法产生系统，由定义的文法规则产生出语言的每个句子出语言的每个句子n方法二：机器识别系统：当一个字符串能被一个语方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则

9、这个字符串是该语言的一个言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语言。句子，否则不属于该语言。现在学习的是第14页，共33页元语言元语言n定义定义：描述语言的语言描述语言的语言例如：各种各样的程序设计语言例如：各种各样的程序设计语言n当人们要解释或讨论程序设计语言本身时，又需要当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语言，即某种程一种语言，被讨论的语言叫做对象语言，即某种程序设计语言，讨论对象语言的语言称为元语言序设计语言，讨论对象语言的语言称为元语言。现在学习的是第15页，共33页BNF（巴科斯范式）巴科斯范式）BNF范式通常被作为讨论

10、某种程序设计语言语法的元语言n:=0|1|2|9 :=“定义为”n:=A|B|C|Z|a|b|z :=|.n通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。nBNF定义了一种语言，其中标识符如上定义。nBNF描述它所定义的语言，为元语言。现在学习的是第16页，共33页n例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。如他是学生。n文法是一种元语言，一种方法，根据文法产生出文法是一种元语言，一种方法，根据文法产生出语言的句子。语言的句子。现在学习的是第17页，共33页三、

11、Chomsky文法体系n例如：BNF:=:=:=:=a|b|z|A|B|Z :=0|1|9将:=改为表示可被代替用I,L,D分别表示标识符、字母、数字;现在学习的是第18页，共33页则上述表达式可以表示为则上述表达式可以表示为 IL IIL IID La|b|.|z D0|1|.9这就是一个文法的生成式集合。这就是一个文法的生成式集合。现在学习的是第19页，共33页nChomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。nP中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符

12、串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而导出来。n可见文法的核心是生成式的集合，它决定了语言中句子的产生。现在学习的是第20页，共33页文法的形式定义n文法G是一个四元组G=(N，T，P，S)，其中N 非终结符的有限集合T 终结符的有限集合 NT=P 形式为的生成式的有限集合。且(NT)*N+(NT)*(NT)*S 起始符 且S N。现在学习的是第21页，共33页n将上例用文法表示G=(N，T，P，S)N=I,L,DT=a,b,c,z,0,1,9P=I,La,D0,D9S=I n文法是语言的产生系统，研究怎样构造文法能产生出符合要求的句子。现在学习的是第22页，共33页四推

13、导与句型1、直接推导设G=（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，则有A=称A直接推导出，或说是A的直接推导。现在学习的是第23页，共33页n设G=(N,T,P,S)是文法，、0、1n、都是（NT）*中的字符串，且=0、=n，其中i直接推导出i+1（0in）,则称序列0=1=2=n是长度为n的推导序列，而=0是长度为0的推导序列。n对推导出记为 ，若推导序列长度大于0，则记为 。n推导序列的每一步，都产生一个字符串，这些字符串一般称为句型。2、推导序列*G G 现在学习的是第24页，共33页3、句型和句子n句型字符串字符串是文法是文法G的句型，当且仅当的句型，当

14、且仅当S ，且且（NT）*。n 句子是是G的句子，当且仅当的句子，当且仅当S ,且且T*。（。（是由是由终结符组成的字符串）终结符组成的字符串）例：例：I=L=a I=IL=LL=zL=zbn句型包含句子*G*G 现在学习的是第25页，共33页4文法产生的语言由文法由文法G产生的语言记为产生的语言记为L(G)。L(G)=|T*且且S 或：或：L(G)中的一个字符串，必是由终结符组成中的一个字符串，必是由终结符组成的，并且是从起始符的，并且是从起始符S推导出来的。推导出来的。*G 现在学习的是第26页，共33页第三节 Chomsky文法体系分类n文法文法 G=(N,T,P,S)；P:其中其中（N

15、T）*N+（NT）*（NT）*属于属于Chomsky文法体系文法体系n该体系对生成式的形式做了一些规定，分为四类，该体系对生成式的形式做了一些规定，分为四类，即即0型、型、1型、型、2型、型、3型文法型文法n0型文法：无限制文法型文法：无限制文法对应的语言：递归可枚举语言，与图灵机等价。现在学习的是第27页，共33页1型文法n也称上下文有关文法（也称上下文有关文法（CSG：Context-sensitive Grammar)生成式的形式为生成式的形式为，其中其中|，（NT）+，（NT）*N+（NT）*n对应的语言：上下文有关语言（对应的语言：上下文有关语言（CSL：Context-sensit

16、ive Language)n若不考虑若不考虑，与线性有界自动机（与线性有界自动机（LBA,Linear Bounded Automaton）等价。等价。现在学习的是第28页，共33页2型文法n也称上下文无关文法（也称上下文无关文法（CFG：Context-free Grammar)A,AN,且且（NT）*n对 应 的 语 言：上 下 文 无 关 语 言对 应 的 语 言：上 下 文 无 关 语 言 （C F L：Context-free Language)。n对应的自动机：下推自动机（对应的自动机：下推自动机（PDA：Pushdown Automaton)。现在学习的是第29页，共33页3型文

17、法也称正则文法也称正则文法n右线性文法（右线性文法（Right-linear Grammar）：）：AB 或或 AA、BN,T*。n左线性文法（左线性文法（Left-linear Grammar）：）：AB或或 AA、BN,T*。n对应的语言：正则语言对应的语言：正则语言n对 应 的 自 动 机：有 限 自 动 机（对 应 的 自 动 机：有 限 自 动 机（F i n i t e Automaton）。）。现在学习的是第30页，共33页例例1：G=(A,B,C,a,b,d,P,A)P:AAB；ABCAAB；Ad；Ba；Cb 是是1型文法。型文法。A=dA=AB=dB=daA=AB=ABB=d

18、BB=daB=daaA=AB=CAAB=bAAB=bdAB=bdCAAB=bdbAAB=bdbdAB=bdbddB=bdbdda现在学习的是第31页，共33页例例2：G=(A,B,C,a,b,c,P,A)P:Aabc AaBbc BbbB BcCbcc bCCb aCaaB aCaa 是是1型文法。型文法。其定义的其定义的 L=anbncn|n1n A=abcn A=aBbc=abBc=abCbcc=aCbbcc=aabbcc =aaBbbcc现在学习的是第32页，共33页例例3：G=(S,B,C,a,b,P,S)P:SaC；SbB；BaS；BbBB Ba；CbS；CaCC；Cb 是是2型文法型文法 n S=aC=ab nS=aC=aaCCnS=aC=abS=abaC=ababS=ababaC=abababnS=bB=bbBB=bbaSB=bbaaCB=bbaabB=bbaaba现在学习的是第33页，共33页