计算理论第2章去某范式版.ppt
《计算理论第2章去某范式版.ppt》由会员分享,可在线阅读,更多相关《计算理论第2章去某范式版.ppt(85页珍藏版)》请在三一文库上搜索。
1、第一部分 自动机与语言,第1章 正则语言 研究内容 有穷自动机 非确定性 正则表达式 非正则语言,第2章 上下文无关文法,研究内容 上下文无关文法概述 下推自动机 非上下文无关语言,上下文无关文法的引入,有穷自动机和正则表达式这两种不同但等价的描述语言的方法,虽然能描述许多语言,但还有一些简单的语言不能用它们描述,如:0n1n | n=0 于是,需引入一种能力更强的描述语言数学模型上下文无关文法,它能够描述某些应用广泛的具有递归结构特征的语言,对任何语言L,有一个字母表,使得L* 。 L的具体组成结构是什么样的? 一个给定的字符串是否为一个给定语言的句子?如果不是,它在结构的什么地方出了错?进
2、一步地,这个错误是什么样的错?如何更正?。 这些问题对有穷语言来说,比较容易解决。 这些问题对无穷语言来说,不太容易解决。 用文法作为相应语言的有穷描述不仅可以描述出语言的结构特征,而且还可以产生这个语言的所有句子,文法(grammar),例:1)哈尔滨是美丽的城市 2)北京是祖国的首都 3)集合是数学的基础 4)形式语言是很抽象的 4个句子的主体结构 =哈尔滨,北京,集合,形式语言 =是美丽的城市,是祖国的首都,是数学的基础,是很抽象的 =。,可以是 或者 。 =北京、哈尔滨、形式语言、集合、美丽的城市、祖国的首都、数学的基础。 =是。 =很抽象的。 把取名为。,表示成形式 是,表示一个语言
3、,需要4种东西 形如的 “符号” 它们表示相应语言结构中某个位置上可以出现的一些内容。每个“符号”对应的是一个集合,在该语言的一个具体句子中,句子的这个位置上能且仅能出现相应集合中的某个元素。所以,这种“符号”代表的是一个语法范畴。 所有的“规则”,都是为了说明的结构而存在,相当于说,定义的就是。, 形如北京的“符号” 它们是所定义语言的合法句子中将出现的“符号”。仅仅表示自身,称为终极符号。 所有的“规则”都呈的形式 在产生语言的句子中被使用,称这些“规则”为产生式。,文法的形式定义,G=(V, , R, S) V为变量(variable)的非空有穷集。AV,A叫做一个语法变量(syntac
4、tic Variable),简称为变量,也可叫做非终极符号(nonterminal)。它表示一个语法范畴(syntactic Category)。 为终极符(terminal)的非空有穷集。a ,a叫做终极符。由于中变量表示语法范畴, 中的字符是语言的句子中出现的字符,所以,有V =。 SSV,为文法G的开始符号(start symbol)。,文法的形式定义,R为产生式(production)的非空有穷集合。R中的元素均具有形式,被称为产生式,读作:定义为。其中(V)+,且中至少有V中元素的一个出现。(V)*。称为产生式的左部,称为产生式的右部。产生式又叫做定义式或者语法规则。,文法例 1,例
5、 : 以下四元组都是文法。 (A,0,1,A01,A0A1,A1A0,A)。 (A,0,1,A0,A0A,A)。 (A,B,0,1,A01,A0A1,A1A0,BAB,B0,A)。 (A,B,0,1,A0,A1,A0A,A1A ,A)。 (S,A,B,C,D, a,b,c,d,#,SABCD,Sabc#,AaaA,ABaabbB,BCbbccC,cCcccC,CDccd#,CDd#,CD#d,S)。,约定, 对一组有相同左部的产生式 1,2 , ,n 可以简单地记为: 1|2|n 读作:定义为1,或者2,或者n。并且称它们为产生式。1,2,n称为候选式(candidate)。, 使用符号 英文
6、字母表较为前面的大写字母,如A,B,C,表示语法变量; 英文字母表较为前面的小写字母,如a,b,c,表示终极符号; 希腊字母,表示由语法变量和终极符号组成的行,推导(derivation),设G= (V, , R, S)是一个文法,如果R,(V )*,则称在G中直接推导出。 G 读作:在文法G中直接推导出。 “直接推导”可以简称为推导(derivation),也称推导为派生。,定义,语言(language) L(G)=w | w *且S * w 句子(sentence) wL(G),w称为G产生的一个句子。 句型(sentential form) G=(V, ,R,S),对于(V)*,如果S
7、* ,则称是G产生的一个句型。,定义,句子w是从S开始,在G中可以推导出来的终极符号行,它不含语法变量。 句型是从S开始,在G中可以推导出来的符号行,它可能含有语法变量。 等价(equivalence) 设有两个文法G1和G2,如果L(G1)= L(G2),则称G1与G2等价。,文法的构造例1,例:构造文法G,使L(G)=0,1,00,11 G1:S0|1|00|11 G2:SA|B|AA|BB,A0,B1 G3:S0|1|0A|1B,A0,B1 G4:SA|B|AA|BB,A0,B1 G5:SA|B|BB,A0,B1,CACS21,C11,C2,文法的构造例2,L=0n|n1 G6:S0|0
8、S L=0n|n0 G7:S|0S L=02n13n|n0 G8:S|00S111,文法的构造例 3,例:构造文法G9,使L(G9)=w|wa,b,z+。 G9:SA|AS Aa|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 用SA|AS生成 An。 不可以用Aa|b|c|z表示。Aa|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 不可以用Aa8表示Aaaaaaaaa。 不能用Aan 表示A可以产生任意多个a。,文法的乔姆斯基体系,文法G=(V, ,R,S) G叫做0型文法(type 0
9、 grammar),也叫做短语结构文法(phrase structure grammar, PSG)。 L(G)叫做0型语言。也可以叫做短语结构语言(PSL)、递归可枚举集(recursively enumerable ,r.e. )。,文法的乔姆斯基体系,G是0型文法。 如果对于R,均有|成立,则称G为1型文法(type 1 grammar),或上下文有关文法(context sensitive grammar,CSG)。 L(G)叫做1型语言(type 1 language)或者上下文有关语言(context sensitive language ,CSL)。,文法的乔姆斯基体系,G是1型
10、文法 如果对于R,均有|,并且V成立,则称G为2型文法(type 2 grammar),或上下文无关文法(context free grammar,CFG)。 L(G)叫做2型语言(type 2 language)或者上下文无关语言(context free language ,CFL)。,文法的乔姆斯基体系,G是2型文法 如果对于R,均具有形式 Aw AwB 其中A,BV,w +。则称G为3型文法(type 3 grammar),也可称为正则文法(regular grammar ,RG)或者正规文法。 L(G)叫做3型语言(type 3 language),也可称为正则语言或者正规语言(re
11、gular language ,RL)。,文法的乔姆斯基体系, 如果一个文法G是RG(3型文法),则它也是CFG(2型文法)、CSG(1型文法)和短语结构文法(0型文法)。反之不一定成立。 如果一个文法G是CFG,则它也是CSG和短语结构文法。反之不一定成立。 如果一个文法G是CSG,则它也是短语结构文法。反之不一定成立。 相应地: RL也是CFL、CSL和短语结构语言。反之不一定成立。,文法的乔姆斯基体系, CFL也是CSL和短语结构语言。反之不一定成立。 CSL也是短语结构语言。反之不一定成立 当文法G是CFG时,L(G)却可以是RL。 当文法G是CSG时,L(G)可以是RL、CSL。 当
12、文法G是短语结构文法时,L(G)可以是RL、CSL和CSL。,定理,定理 : L是RL(正则语言)的充要条件是存在一个文法,该文法产生语言L,并且它的产生式要么是形如:Aa的产生式,要么是形如AaB的产生式。其中A、B为语法变量,a为终极符号。,2.1 上下文无关文法概述,文法G=(V, ,R,S)被称为是上下文无关文法或2型文法。 如果对于R,均有|,并且V成立。 关键:对于AV,如果AP,则无论A出现在句型的任何位置,我们都可以将A替换成,而不考虑A的上下文。 L(G)叫做2型语言(type 2 language)或者上下文无关语言(context free language ,CFL)。
13、,上下文无关文法示例,上下文无关文法示例,2.1.1 上下文无关文法的形式化定义,定义2.1 上下文无关文法是一个4元组 G=(V,R,S) V: 一个有穷集,称为变元集 : 一个有穷集 (V=) ,称为终结符集 R: 有穷规则集, V (V)* 规则是 左一右多,或一分为多 SV : 起始变元 文法 G的语言可以表示为 L(G): L(G) = w* | S * w ,上下文无关文法举例,2.1.2 上下文无关文法举例,2.1.3 设计上下文无关文法,2.1.3 设计上下文无关文法,利用正则 考察子串 利用递归,2.1.4 岐义性,如果文法以不同的方式产生同一个字符串,则称文法歧义地产生这个
14、字符串,如果一个文法歧义地产生某个字符串,则称这个文法是歧义的,2.1.4 岐义性,定义2.4 如果字符串w在上下文无关文法G中有两个以上不同的最左派生,则称G歧义地产生字符串w,如果文法G歧义地产生某个字符串,则称G是歧义的; 注意:有时对于一个歧义文法,能够找到一个产生相同语言的非歧义文法,但是,某些上下文无关语言只能用歧义文法产生,这样的语言称为固有歧义的。,2.1.5 乔姆斯基范式Chomsky Normal Form,定义2.5 称一个上下文无关文法 G = (V,R,S) 为乔姆斯基范式,如果它的每一个规则具有如下形式 A BC 一分为二 或 A a 或终极化 其中, AV and
15、 B,CV S, and a ,2.1.5 乔姆斯基范式Chomsky Normal Form,定理2.6 任一上下文无关文法 G = (V,R,S) 为语言都可以用一个乔姆斯基范式的上下文无关文法产生,证明思路:1)添加一个新的起始变元S0; 和规则S0S 2)考虑所有的诸如A 规则; R uAv, 添加R uv; R uAvAw, 添加R uvAw; R uAvw; R uvw R A, 添加R 3)处理所有的单一规则; 4)添加新的变元和规则,把留下的所有规则转换成合适的变元;,例,例,试将下列文法转换成等价的 CNF。 SbA | aB AbAA | aS | a BaBB | bS
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 理论 章去某 范式
链接地址:https://www.31doc.com/p-2654233.html