形式语言与自动机理论--第六章(蒋宗礼)

形式语言与自动机理论FormalLanguagesandAutomataTheory蒋宗礼课程目的和基本要求•课程性质–技术基础•基础知识要求–数学分析（或者高等数学），离散数学•主要特点–抽象和形式化–理论证明和构造性–基本模型的建立与性质课程目的和基本要求•本专业人员4种基本的专业能力–计算思维能力–算法的设计与分析能力–程序设计和实现能力–计算机软硬件系统的认知、分析、设计与应用能力•计算思维能力–逻辑思维能力和抽象思维能力–构造模型对问题进行形式化描述–理解和处理形式模型课程目的和基本要求•知识–掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。•能力–培养学生的形式化描述和抽象思维能力。–使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。主要内容•语言的文法描述。•RL–RG、FA、RE、RL的性质。•CFL–CFG(CNF、GNF)、PDA、CFL的性质。•TM–基本TM、构造技术、TM的修改。•CSL–CSG、LBA。教材及主要参考书目1.蒋宗礼，姜守旭.形式语言与自动机理论.北京：清华大学出版社，2003年2.JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,20013.JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979第6章上下文无关语言•Gbra：SS(S)|ε•L(Gbra)不是RL,是CFLhhnnnnnn10......1010221`1•高级程序设计语言的绝大多数语法结构都可以用上下文无关文法(CFG)描述。。•BNF(巴科斯范式：Backusnormalform，又叫Backus-naurform)。第6章上下文无关语言•主要内容–关于CFL的分析•派生和归约、派生树–CFG的化简•无用符、单一产生式、空产生式–CFG的范式•CNF•GNF–CFG的自嵌套特性第6章上下文无关语言•重点–CFG的化简。–CFG到GNF的转换。•难点–CFG到GNF的转换，特别是其中的用右递归替换左递归的问题。6.1上下文无关语言•文法G=(V，T，P，S)被称为是上下文无关的。如果除了形如Aε的产生式之外，对于αβ∈P，均有|β|≥|α|，并且α∈V成立。•关键：对于A∈V，如果Aβ∈P，则无论A出现在句型的任何位置，我们都可以将A替换成β，而不考虑A的上下文。6.1.1上下文无关文法的派生树•算术表达式的文法Gexp1：EE+T|E-T|TTT*F|T/F|FFF↑P|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E6.1.1上下文无关文法的派生树•算术表达式x+x/y↑2的不同派生EE+TT+TF+TP+Tx+Tx+T/Fx+F/Fx+P/Fx+x/Fx+x/F↑Px+x/P↑Px+x/y↑Px+x/y↑2EE+TE+T/FE+T/F↑PE+T/F↑2E+T/P↑2E+T/y↑2E+F/y↑2E+P/y↑2E+x/y↑2T+x/y↑2F+x/y↑2P+x/y↑2x+x/y↑2EE+TT+TT+T/FF+T/FF+T/F↑PP+T/F↑Px+T/F↑Px+F/F↑Px+F/F↑2x+F/P↑2x+P/P↑2x+P/y↑2x+x/y↑26.1.1上下文无关文法的派生树•文法Gexp1句子x+x/y↑2的结构。6.1.1上下文无关文法的派生树•派生树(derivationtree)–一棵(有序)树(orderedtree)–树的每个顶点有一个标记X，且X∈V∪T∪{ε}–树根的标记为S；–如果非叶子顶点v标记为A，v的儿子从左到右依次为v1，v2，…，vn，并且它们分别标记为X1，X2，…，Xn，则AX1X2…Xn∈P；–如果X是一个非叶子顶点的标记，则X∈V；–如果顶点v标记为ε，则v是该树的叶子，并且v是其父顶点的惟一儿子。6.1.1上下文无关文法的派生树•别称–生成树–分析树(parsetree)–语法树(syntaxtree)•顺序–v1，v2是派生树T的两个不同顶点，如果存在顶点v，v至少有两个儿子，使得v1是v的较左儿子的后代，v2是v的较右儿子的后代，则称顶点v1在顶点v2的左边，顶点v2在顶点v1的右边。6.1.1上下文无关文法的派生树•结果(yield)•派生树T的所有叶子顶点从左到右依次标记为X1，X2，…，Xn，则称符号串X1X2…Xn是T的结果。•一个文法可以有多棵派生树，它们可以有不同的结果。•句型α的派生树：“G的结果为α的派生树”。6.1.1上下文无关文法的派生树•派生子树(subtree)•满足派生树定义中除了对跟结点的标记的要求以外各条的树叫派生子树(subtree)。•如果这个子树的根标记为A，则称之为A子树。•惟一差别是根结点可以标记非开始符号。6.1.1上下文无关文法的派生树定理6-1设CFGG=(V，T，P，S)，S*α的充分必要条件为G有一棵结果为α的派生树。证明：•证一个更为一般的结论：对于任意A∈V，A*α的充分必要条件为G有一棵结果为α的A-子树。•充分性：设G有一棵结果为α的A-子树，非叶子顶点的个数n施归纳，证明A*α成立。6.1.1上下文无关文法的派生树•设A-子树有k+1个非叶子顶点，根顶点A的儿子从左到右依次为v1，v2，…，vm，并且它们分别标记为X1，X2，…，Xm。•AX1X2…Xm∈P。•以X1，X2，…，Xm为根的子树的结果依次为α1，α2，…，αm。•X1，X2，…，Xm为根的子树的非叶子顶点的个数均不大于k。6.1.1上下文无关文法的派生树X1*α1X2*α2…Xm*αm而且α=α1α2…αm6.1.1上下文无关文法的派生树AX1X2…Xm*α1X2…Xm*α1α2…Xm…*α1α2…αm6.1.1上下文无关文法的派生树6.1.1上下文无关文法的派生树•必要性–设Anα，现施归纳于派生步数n，证明存在结果为α的A-子树。设n≤k(k≥1)时结论成立，往证当n=k+1时结论也成立：令Ak+1α，则有：AX1X2…Xm*α1X2…Xm*α1α2…Xm…*α1α2…αm6.1.1上下文无关文法的派生树6.1.1上下文无关文法的派生树•例6-1设Gbra：SS(S)|ε，(()(()))和(S)((S))的派生树。6.1.1上下文无关文法的派生树•关于标记ε的结点6.1.1上下文无关文法的派生树•最左派生(leftmostderivation)–α的派生过程中，每一步都是对当前句型的最左变量进行替换。•左句型(leftsentencialform)–最左派生得到的句型可叫做左句型。•最右归约(rightmostreduction)–与最左派生对相的归约叫做最有归约。6.1.1上下文无关文法的派生树•最右派生(rightmostderivation)–α的派生过程中，每一步都是对当前句型的最右变量进行替换。•右句型(rightsentencialform)–最右派生得到的句型可叫做右句型。•最左归约(leftmostreduction)–与最左派生对相的归约叫做最右归约。6.1.1上下文无关文法的派生树•规范派生(normalderivation)–最右派生。•规范句型(normalsentencialform)–规范派生产生的句型。•规范归约(normalreduction)–最左归约。6.1.1上下文无关文法的派生树定理6-2如果α是CFGG的一个句型，则G中存在α的最左派生和最右派生。证明：基本思路：对派生的步数n施归纳，证明对于任意A∈V，如果Anα，在G中，存在对应的从A到α的最左派生：An左α。6.1.1上下文无关文法的派生树AX1X2…Xm*α1X2…Xm*α1α2…Xm…*α1α2…αmA左X1X2…Xm*左α1X2…Xm*左α1α2…Xm…*左α1α2…αm同理可证，句型α有最右派生。6.1.1上下文无关文法的派生树定理6-3如果α是CFGG的一个句型，α的派生树与最左派生和最右派生是一一对应的，但是，这棵派生树可以对应多个不同的派生。6.1.2二义性•简单算术表达式的二义性文法Gexp2：EE+E|E-E|E/E|E*EEE↑E|(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E6.1.2二义性EE+Ex+Ex+E/Ex+x/Ex+x/E↑Ex+x/y↑Ex+x/y↑2句子x+x/y↑2在文法中的三个不同的最左派生EE/EE+E/Ex+E/Ex+x/Ex+x/E↑Ex+x/y↑Ex+x/y↑2EE↑EE/E↑EE+E/E↑Ex+E/E↑Ex+x/E↑Ex+x/y↑Ex+x/y↑26.1.2二义性对应3个不同的语法树6.1.2二义性•二义性(ambiguity)•CFGG=(V，T，P，S)，如果存在w∈L(G)，w至少有两棵不同的派生树，则称G是二义性的。否则，G为非二义性的。•二义性的问题是不可解的(unsolvable)问题。6.1.2二义性•例6-2用其他方法消除二义性。Gifa：SifEthenSelseS|ifEthenSGifm：S→U|MU→ifEthenSU→ifEthenMelseUM→ifEthenMelseM|SGifh：S→TS|CSC→ifEthenT→CSelse6.1.2二义性•例6-3设Lambiguity={0n1n2m3m|n,m≥1}∪{0n1m2m3n|n,m≥1}可以用如下文法产生语言Lambiguity：G：SAB|0C3A01|0A1B23|2B3C0C3|12|1D2D12|1D2语言Lambiguity不存在非二义性的文法。6.1.2二义性•固有二义性的(inherentambiguity)•如果语言L不存在非二义性文法，则称L是固有二义性的，又称L是先天二义性的。•文法可以是二义性的。•语言可以是固有二义性的。6.1.3自顶向下的分析和自底向上的分析•自顶向下的分析方法–通过考察是否可以从给定文法的开始符号派生出一个符号串，可以判定一个符号串是否为该文法的句子。•例–SaAb|bBa–AaAb|bBa–Bdaabdabb的派生树的自顶向下的“生长”过程6.1.3自顶向下的分析和自底向上的分析•自底向上的分析方法–通过考察是否可以将一个符号串归约为给定文法的开始符号，完成判定一个符号串是否为该文法的句子的任务。•和归约与派生是互逆过程相对应，自顶向下的分析与自底向上的分析互逆的分析过程。aabdabb的派生树的自底向上的“生长”过程6.2上下文无关文法的化简•如下文法含有无用的“东西”G1：S0|0A|EAε|0A|1A|BB_CC0|1|0C|1CD1|1D|2DE0E2|E02•去掉无用“东西”后的文法G2：S0|0AAε|0A|1A|BB_CC0|1|0C|1C6.2上下文无关文法的化简•去掉产生式Aε后的文法G3：S0|0AA0|1|0A|1A|BB_CC0|1|0C|1C•去掉产生式AB后的文法G4：S0|0AA0|1|0A|1A|_CC0|1|0C|1C•可以去掉文法中的无用符号、ε产生式和单一产生式。6.2.1去无用符号•无用符号(uselesssymbol)–对于任意X∈V∪T，如果存在w∈L(G)，X出现在w的派生过程中，即存在α，β∈(V∪T