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

《形式语言与自动机理论--第六章(蒋宗礼)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、形式语言与自动机理论FormalLanguagesandAutomataTheory蒋宗礼课程目的和基本要求课程性质技术基础基础知识要求数学分析（或者高等数学），离散数学主要特点抽象和形式化理论证明和构造性基本模型的建立与性质课程目的和基本要求本专业人员4种基本的专业能力计算思维能力算法的设计与分析能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述理解和处理形式模型课程目的和基本要求知识掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。能力培养学生的形式化描述和抽象思维能

2、力。使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。主要内容语言的文法描述。RLRG、FA、RE、RL的性质。CFLCFG(CNF、GNF)、PDA、CFL的性质。TM基本TM、构造技术、TM的修改。CSLCSG、LBA。教材及主要参考书目蒋宗礼，姜守旭.形式语言与自动机理论.北京：清华大学出版社，2003年JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addis

3、on-WesleyPublishingCompany,2001JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979第6章上下文无关语言Gbra：SS(S)

4、εL(Gbra)不是RL,是CFL高级程序设计语言的绝大多数语法结构都可以用上下文无关文法(CFG)描述。。BNF(巴科斯范式：Backusnormalform，又叫Backus-naurform)。第6章上下文无关语言主要内容关于CFL

5、的分析派生和归约、派生树CFG的化简无用符、单一产生式、空产生式CFG的范式CNFGNFCFG的自嵌套特性第6章上下文无关语言重点CFG的化简。CFG到GNF的转换。难点CFG到GNF的转换，特别是其中的用右递归替换左递归的问题。6.1上下文无关语言文法G=(V，T，P，S)被称为是上下文无关的。如果除了形如Aε的产生式之外，对于αβ∈P，均有

6、β

7、≥

8、α

9、，并且α∈V成立。关键：对于A∈V，如果Aβ∈P，则无论A出现在句型的任何位置，我们都可以将A替换成β，而不考虑A的上下文。6.1.1上下文无关文法的派生树算术表达式的文法Gexp1：EE+T

10、E-T

11、TTT

12、*F

13、T/F

14、FFF↑P

15、PP(E)

16、N(L)

17、idNsin

18、cos

19、exp

20、abs

21、log

22、intLL,E

23、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

24、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标记为ε，

25、则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的结果。一个文法可以有多棵派生树，它