计算理论第2章去某范式版.ppt

第一部分 自动机与语言,第1章 正则语言 研究内容 有穷自动机 非确定性 正则表达式 非正则语言,第2章 上下文无关文法,研究内容 上下文无关文法概述 下推自动机 非上下文无关语言,上下文无关文法的引入,有穷自动机和正则表达式这两种不同但等价的描述语言的方法，虽然能描述许多语言，但还有一些简单的语言不能用它们描述，如：0n1n | n=0 于是，需引入一种能力更强的描述语言数学模型上下文无关文法，它能够描述某些应用广泛的具有递归结构特征的语言,对任何语言L，有一个字母表，使得L* 。 L的具体组成结构是什么样的？ 一个给定的字符串是否为一个给定语言的句子?如果不是，它在结构的什么地方出了错？进一步地，这个错误是什么样的错？如何更正？。 这些问题对有穷语言来说，比较容易解决。 这些问题对无穷语言来说，不太容易解决。 用文法作为相应语言的有穷描述不仅可以描述出语言的结构特征，而且还可以产生这个语言的所有句子,文法(grammar),例：1）哈尔滨是美丽的城市 2）北京是祖国的首都 3）集合是数学的基础 4）形式语言是很抽象的 4个句子的主体结构 =哈尔滨，北京，集合，形式语言 =是美丽的城市，是祖国的首都，是数学的基础，是很抽象的 =。,可以是 或者 。 =北京、哈尔滨、形式语言、集合、美丽的城市、祖国的首都、数学的基础。 =是。 =很抽象的。 把取名为。,表示成形式 是,表示一个语言，需要4种东西 形如的 “符号” 它们表示相应语言结构中某个位置上可以出现的一些内容。每个“符号”对应的是一个集合，在该语言的一个具体句子中，句子的这个位置上能且仅能出现相应集合中的某个元素。所以，这种“符号”代表的是一个语法范畴。 所有的“规则”，都是为了说明的结构而存在，相当于说，定义的就是。, 形如北京的“符号” 它们是所定义语言的合法句子中将出现的“符号”。仅仅表示自身，称为终极符号。 所有的“规则”都呈的形式 在产生语言的句子中被使用，称这些“规则”为产生式。,文法的形式定义,G=(V, , R, S) V为变量(variable)的非空有穷集。AV，A叫做一个语法变量(syntactic Variable)，简称为变量，也可叫做非终极符号(nonterminal)。它表示一个语法范畴(syntactic Category)。 为终极符(terminal)的非空有穷集。a ，a叫做终极符。由于中变量表示语法范畴， 中的字符是语言的句子中出现的字符，所以，有V =。 SSV，为文法G的开始符号(start symbol)。,文法的形式定义,R为产生式(production)的非空有穷集合。R中的元素均具有形式，被称为产生式，读作：定义为。其中(V)+，且中至少有V中元素的一个出现。(V)*。称为产生式的左部，称为产生式的右部。产生式又叫做定义式或者语法规则。,文法例 1,例 ： 以下四元组都是文法。 (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)。, 使用符号 英文字母表较为前面的大写字母，如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 * ，则称是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|0S 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 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型文法 如果对于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)，也可称为正则语言或者正规语言(regular 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。 当文法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)。,上下文无关文法示例,上下文无关文法示例,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 岐义性,如果文法以不同的方式产生同一个字符串，则称文法歧义地产生这个字符串，如果一个文法歧义地产生某个字符串，则称这个文法是歧义的,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 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 | b,先引入变量Ba，Bb和产生式Baa，Bbb ，完成第一步变换。 SBbA | BaB ABbAA | BaS | a BBaBB | BbS | b Baa Bbb,引入新变量B1、B2 SBbA | BaB ABbB1 | BaS | a BBaB2 | BbS | b Baa Bbb B1AA B2BB,不能因为原来有产生式A a和B b而放弃引进变量Ba 、Bb和产生式Baa 、Bbb。 L(A)=x | xa，b+ & x中a的个数比b的个数恰多1个。 L(B)=x | xa，b+ & x中b的个数比a的个数恰多1个。 L(Ba)= a 。 L(Bb)= b 。,习题,试将下列文法转换成等价的 CNF。 SaBB | bAA BaBa | aa | AbbA | ,2.2 下推自动机Pushdown Automata,下推自动机PDA：描述CFL（上下文无关语言）的设备 PDA： “硬件” 增加了栈（先进后出），使其能识别某些非正则语言 PDA： 与上下文无关文法等价,有穷自动机的物理模型,PDA的物理模型,FSC：表示状态和转移函数 栈：“先进后出”的存储设备，能保存无限的信息量 推入：向栈写一个符号 弹出：从栈中删除一个符号,例,例,非形式化地描述关于语言0n1n | n=0的PDA如何工作的：,PDA 的形式化描述,输入 w = 00100100111100101,内部状态集合 State set Q,PDA M 读带 w 且 作栈操作取决于 - 输入 wi ,输入字母表 - 栈 sj ,栈字母表 - 状态 qk Q 状态集合 PDA M: - 调转到一个新的状态, - 推入元素 (非确定性地),PDA的基本结构,PDA应该含有三个基本结构 存放输入符号串的输入带。 存放文法符号的栈。 有穷状态控制器。 PDA的动作 在有穷状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作，在有的时候，不需要考虑输入符号。,下推自动机M被定义为6元组 (Q，q0，F)，这里Q，和F都是有穷集合，并且： Q 是状态集 是输入字母表 栈字符表 q0 Q是起始状态 F Q是接受状态集 是状态转移函数 相当于3种语句goto, push ,pop : Q P (Q ) = = ,2.2.1 PDA 的形式化定义,(q，a，Z)=(p1，1)，(p2，2)，(pm，m) 表示M在状态q，栈顶符号为Z时，读入字符a，对于i=1，2，m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将i中的符号从右到左依次压入栈，然后将读头向右移动一个带方格而指向输入字符串的下一个字符。,(q，Z)=(p1，1)，(p2，2)，(pm，m) 表示M进行一次-移动(空移动)，即M在状态q，栈顶符号为Z时，无论输入符号是什么，对于i=1，2，m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将i中的符号从右到左依次压入栈，读头不移动。,PDA 的计算过程,一台下推自动机M接受输入w，如果能够把w写成w=w1w2wm，这里每一个wi ，并且存在状态序列r0, r1, , rm Q和字符串序列s0, s1, , sm T*满足下述3个条件，字符串si是M在计算的接受分支中的栈内容序列。 r0 q0 且s0， 对于i=0, , m-1，有（ri+1 ，b） (ri， wi+1 ，a)其中si=at, si+1=bt, a, b T 和t T*； rm F,例2.9 : L = 0n1n | n0 背景： 检查左右括号(0,1)是否 配对 PDA 首先把 “ $ 0n ” 推入栈. $ 栈底符号，压箱钱 ，表示后来压入栈的存款用完了。 然后，当读到“1n”, 0被弹出. 栈顶对比，左右括号配对，则同归于尽， 最后, 如果“$”留在栈顶，则接受,2.2.2 PDA 举例,状态图描述,用“a, b c”表示当机器从输入中读a时可用c替换栈顶的符号b。 若a是，则机器作这个转移，而不读取输入中的任何符号。 若b是，则机器作这个转移，而不读栈中的任何符号，也不从栈中弹出任何符号。若c是，则不在栈中写任何符号。,形式化定义,w = 000111,w = 0101,例： 构造一台识别下述语言的PDA M： aibjck i, j, k0 且 i=j 或 i=k,例,例 ： 构造接受L=wwT|w0,1*的PDA。,确定的(deterministic)PDA,PDA在每一个状态q和一个栈顶符号下的动作都是惟一的。 关键 对于(q，Z)Q，M此时如果有非空移动，就不能有空移动。 每一种情况下的移动都是惟一的。 非确定的PDA和确定型PDA识别能力不同，非确定型PDA能识别确定型PDA不能识别的语言,2.2.3与上下文无关文法的等价性,定理.12: 一个语言是上下文无关的，当且仅当存在一台PDA识别它。 L是CFL L被PDA接受,两步: 1)引理. 如果一个语言是上下文无关的，则存在一台PDA识别它 部分 2)引理.5 如果一个语言被一台PDA识别，则它是上下文无关的 部分 若干教材都说 此定理容易证明 但又略去证明，此定理的证明 适合静心自学，不适合课堂讲解 。 可以先承认结论， 读第二遍时再深入理解,引理2.13 的证明（）,引理2.13 如果一个语言是上下文无关的，则存在一台下推自动机识别它。 证明思路 设A 是CFL，根据定义，存在一个CFG G产生它。说明如何把G转换成一台等价的PDA P。 确定是否存在关于输入w的派生PDA P当G产生w时，接受这个输入。 派生是当文法产生一个字符串时的替换序列，派生的每一步产生一个变元和终结符的中间字符串。 设计P，以确定是否有一系列使用G的规则替换，能够从起始变元导出w 检验是否有关于w的派生。 困难在于判断要替换， PDA的非确定性使得它能够猜想出正确的替换序列， 在派生的每一步，非确定地选择关于某个变元的一条规则，并且对这个变元做替换。,P的非形式描述如下： 1) 把标记符$和起始变元放入栈中； 2）重复下述步骤： 如果栈顶是变元A，则非确定地选择一个关于A的规则，并且把A替换成这条规则右边的字符串； 如果栈项是终结符a，则读输入中的下一个符号，并且把它与a进行比较。如果它们匹配，则重复，如果它们不匹配，则这个非确定性分支拒绝； 如果栈顶是符号$，则进入接受状态，如果此刻输入已全部读完，则接受这个输入。,1）初始化栈，把符号$和S推入栈； 2） a)栈顶是个变元；令(qloop, , A)(qloop, w) A w是R中的一条规则 b)栈顶是个终结符。令(qloop, a, a) (qloop, ) c)栈顶是空栈标记符$。令(qloop, , $)(qaccept, ) ,CFG G 转换成PDA P 例：把下述CFG G转换成一台PDA： SaTb b TTa ,引理2.15的证明（）自学,引理2.15 如果一个语言被一台下推自动机识别，则它是上下文无关的。 证明思路 现有一台PDA P，要构造一个CFG G，它产生P接受的所有字符串。换言之，如果一个字符串能使P从它的起始状态转移到一个接受状态，则G应该产生这个字符串。 为了获得这个结果，我们设计一个能做更多事情的文法。对于P的每一对状态p和q，文法有一个变元Apq。它产生所有能够把P从p和空栈一块带到q和空栈的字符串。可以看出不管栈的内容是什么，这样的字符串也能够把P从p带到q，并且保持栈的内容在状态q和在状态p时样。,引理2.15 的证明（）,为简化工作，对P作修改，使其具有以下三个特点。 1）有唯一的接受状态qaccept 。 2）在接受之前清空栈。 3）每一个转移把一个符号推入栈(推入动作)，或者把一个符号弹出栈(弹出动作)，但不同时做这两个动作。 使P具有特点1和2较容易，使P具有特点3就要把每一个同时弹出和推入的转移替换成两个转移，中间要经过一个新的状态；把每一个既不弹出也不推入的转移替换成两个转移，先推入任意一个栈符号，然后再把它弹出。,引理2.1 证明（3）,设计G，使得Apq产生把P从p带到q并且以空栈开始和结束的所有字符串，了解P对这样的字符串如何运行。 对于任一的字符串x，P的每个动作是推入或是弹出，但对空栈不能弹出，对x的第一个动作一定是推入。因结束时栈空，对x的最后一个动作一定是弹出。 在P对x的计算过程 两情况：仅在开始和结束时，栈是空的；或者除开始和结束时之外，在计算中的某个地方，栈变成空的。如是前情况，最后弹出的符号一定就是开始时推入的那个符号。用规则ApqaArsb模拟前一种情况，其中a是在做第一个动作时读的输入符号，b是在做最后一个动作时读的输入符号，r是跟在p后面的状态，s是q的前一个状态。用规则ApqAprArq模