形式语言与自动机理论(蒋宗礼)教学课件.pptVIP

课程目的和基本要求?课程性质–技术基础?基础知识要求–数学分析（或者高等数学），离散数学?主要特点–抽象和形式化–理论证明和构造性–基本模型的建立与性质

课程目的和基本要求?本专业人员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

第7章下推自动机?PDA描述CFL，所以它应该与CFG等价。?PDA应该包含FA的各个元素，或者包含那些可以取代FA的各个元素的功能的元素。?PDA按照最左派生的派生顺序，处理处于当前句型最左边的变量，因此，需要采用栈作为其存储机构。?按照FA的“习惯”，PDA用终态接受语言。?模拟GNF的派生PDA用空栈接受语言。

第7章下推自动机?主要内容–PDA的基本概念。–PDA的构造举例。–用终态接受语言和用空栈接受语言的等价性。–PDA是CFL的接受器。?重点–PDA的基本定义及其构造，PDA是CFL的等价描述。?难点–根据PDA构造CFG。

7.1基本定义?PDA的物理模型

7.1基本定义?PDA应该含有三个基本结构–存放输入符号串的输入带。–存放文法符号的栈。–有穷状态控制器。?PDA的动作–在有穷状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作，在有的时候，不需要考虑输入符号。

7.1基本定义?下推自动机(pushdownautomaton，PDA)M=(Q，∑，Γ，δ，q，Z，F)00Q——状态的非空有穷集合。?q∈Q，q称为M的一个状态(state)；∑——输入字母表(inputalphabet)。要求M的输入字符串都是∑上的字符串；Γ——栈符号表(stackalphabet)。?A∈Γ，叫做一个栈符号；

7.1基本定义?Z——Z∈Γ叫做开始符号(startsymbol)00是M启动时候栈内惟一的一个符号。所以，习惯地称其为栈底符号；?q——q∈Q，是M的开始状态(initialstate)，0也可叫做初始状态或者启动状态；0?F——F?Q，是M的终止状态(finalstate)集合，简称为终态集。?q∈F，q称为M的终止状态，也可称为接受状态(acceptstate)，简称为终态。

7.1基本定义?δ——状态转移函数(transitionfunction)，有时候又叫做状态转换函数或者移动函数。δ：Q×(∑∪{ε})×Γ?

7.1基本定义δ(q，a，Z)={(p，γ)，(p，γ)，…，1122(p，γ)}mm?表示M在状态q，栈顶符号为Z时，读入字符a，对于i=1，2，…，m，可以选择地将状态变成p，并将栈顶符号Z弹出，将γ中ii的符号从右到左依次压入栈，然后将读头向右移动一个带方格而指向输入字符串的下一个字符。

7.1基本定义δ(q，ε，Z)={(p，γ)，(p，γ)，…，1122(p，γ)}mm?表示M进行一次ε-移动(空移动)，即M在状态q，栈顶符号为Z时，无论输入符号是什么，对于i=1，2，…，m，可以选择地将状态变成p，并将栈顶符号Z弹出，将γ中的ii符号从右到左依次压入栈，读头不移动。

7.1基本