1、1-绪论绪论n 课程信息课程信息n 为什么学习形式语言与自动机为什么学习形式语言与自动机n 形式语言与自动机概述及应用形式语言与自动机概述及应用n 课程内容及要求课程内容及要求2-专业基础课专业基础课 -上世纪上世纪 60 60 年代末、年代末、7070年代初，年代初，研究的高研究的高峰峰-之后，向应用领域渗透，之后，向应用领域渗透，研究生课程研究生课程-近几年，近几年，本科阶段的专业基础课本科阶段的专业基础课 专业工作者必须的理论素养专业工作者必须的理论素养 -计算模型计算模型 计算机（不）能够做什么计算机（不）能够做什么 -问题分类问题分类 计算的复杂性，算法分析计算的复杂性，算法分析 -
2、形式系统形式系统 建模工具（状态机建模工具（状态机 ）-抽象描述抽象描述 形式文法、形式表达式形式文法、形式表达式 课课 程程 性性 质质3-相 关 课 程先修课程先修课程 -离散数学离散数学（数理逻辑，集合论）（数理逻辑，集合论）-计算机导论与程序设计、数据结构计算机导论与程序设计、数据结构 后续课程后续课程 -编译原理编译原理 其它相关课程其它相关课程 模式识别、算法分析模式识别、算法分析 4-n教材教材：形式语言与自动机形式语言与自动机 王柏王柏 杨娟杨娟 编著编著 北京邮电大学出版社北京邮电大学出版社 2003.15-经 典 参 考 书 书名书名 Introduction to Aut
3、omata Theory,Languages,and Computation （Second Edition）作者作者 John E.Hopcroft （Cornell）Rajeev Motwani （Stanford）Jefferey D.Ullman （Stanford）出版社出版社 Addison Wesley （2001）清华大学出版社清华大学出版社 （影印版）（影印版）First Edition 中译本中译本自动机理论、语言和计自动机理论、语言和计算导引算导引 徐美瑞徐美瑞 等译等译 科学出版社，科学出版社，1990 John.E.Hopcroft,the Turing Awardw
4、inner in 1986.6-其它参 考 书 自动机理论及其应用自动机理论及其应用 何成武何成武 科学出版社科学出版社19901990形式语言及其句法分析形式语言及其句法分析 美美A.V.A.V.阿霍阿霍 等等 科学出版社科学出版社1987 1987 形式语言形式语言 王兵山，吴兵王兵山，吴兵 编编 国防工业大学出版社，国防工业大学出版社，19881988 形式语言与自动机形式语言与自动机 陈有祺陈有祺 编著编著 南开大学出版社，天津，南开大学出版社，天津，19991999 7-2、为什么学习形式语言与自动机为什么学习形式语言与自动机n形式语言与自动机是计算机科学的基础理论形式语言与自动机是
5、计算机科学的基础理论之一，是计算机学科的专业基础课。之一，是计算机学科的专业基础课。n在人工智能、电信领域等有广泛的应用。在人工智能、电信领域等有广泛的应用。n通过一些定理的证明和应用，对大家进行思通过一些定理的证明和应用，对大家进行思维训练，从而为今后学习通信软件，协议工维训练，从而为今后学习通信软件，协议工程，编译技术，人工智能等内容提供理论基程，编译技术，人工智能等内容提供理论基础。础。8-2、为什么学习形式语言与自动机为什么学习形式语言与自动机n对客观世界的科学研究：目的在于把抽象数对客观世界的科学研究：目的在于把抽象数学的形式化体系发展成为与现实生活相似的学的形式化体系发展成为与现实
6、生活相似的理论模型，从而提供一种通用结构来描述、理论模型，从而提供一种通用结构来描述、理解和解决问题。理解和解决问题。n计算机科学：是关于计算知识的有系统的整计算机科学：是关于计算知识的有系统的整体。体。9-2、为什么学习形式语言与自动机为什么学习形式语言与自动机n计算机科学的两个主要部分：n构成计算基础的一些基本概念和模型；n设计计算系统(软件和硬件)的工程技术（设计理论的应用）n本课程着重介绍第一部分（涉及到一些第二部分的应用），通过形式化技术对大家进行思维训练，为今后的学习打好理论基础。10-3 3、形式语言与自动机概述及应用、形式语言与自动机概述及应用n本门课程将围绕着什么是形式语言、
7、什么是自动机、以及形式语言和自动机的相互关系进行阐述。n核心内容-有限状态自动机，正规语言，正规表达式-上下文无关文法，上下文无关语言，下推 自动机-图灵机，计算问题分类11-3.1 形式语言n什么是形式语言什么是形式语言n形式语言:形式化描述的字母表上的字符串的集形式化描述的字母表上的字符串的集合。合。n字母表：字符的有限集合。ne.g.：26个英文字母构成的字母表。n字符串：字母表中的字符构成的有限序列。ne.g.hello,afjhkfyu 12-为什么用形式语言为什么用形式语言n自然语言自然语言：人们平时说话时所使用的一种语：人们平时说话时所使用的一种语言，不同的国家和民族有着不同的语
8、言。言，不同的国家和民族有着不同的语言。n形式语言形式语言n通过人们公认的符号，表达方式所描述的通过人们公认的符号，表达方式所描述的一种语言，是一种通用语言，没有国籍之一种语言，是一种通用语言，没有国籍之分。分。n形式语言是某个字母表上的字符串的集合，形式语言是某个字母表上的字符串的集合，有一定的描述范围。有一定的描述范围。13-为什么用形式语言为什么用形式语言n例例1：汉语：汉语：用数用数字、符号等形式化的东西来描述语言字、符号等形式化的东西来描述语言n我吃饭我吃饭 语法正确语法正确n我饭吃我饭吃 语法错误语法错误n饭吃我饭吃我 语法正确，语义错误语法正确，语义错误14-为什么用形式语言为什
9、么用形式语言n例2：T为PASCAL语言所用的全部符号的集合。n正确的PASCAL程序就是T上的语言。n例3：在字母表T=a上，L=a 2n+1|n=0 n表示任意一对aa(包括0对)后跟一个a的字符串。（即含有奇数个a的字符串。）15-为什么用形式语言为什么用形式语言n形式语言的最初起因：语言学家（Chomsky）想用一套形式化方法来描述语言。n形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。n最初的应用：编译 让计算机按照语法规则将高级语言方便地翻译成机器语言。16-为什么用形式语言为什么用形式语言n现在：已广泛应用在人工智能、图象处理、通信协议、通信软件等多个领域n在计算机理论
10、科学方面：是可计算理论（算法在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。17-为什么用形式语言为什么用形式语言n比尔.盖茨：人类计算的未来是让计算机能够看、听、学，能用自然语言与人类交流 n形式化非常重要18-3.2.3.2.自动机自动机n什么是自动机？具有离散输入输出的数学模型。包括：n输入装置读头+输入带n控制部件。状态转移n存储单元n大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛。19-3.2.3.2.自动机自动机n自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作
11、过程。n状态状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”n自动机的本质自动机的本质：根据状态、输入和规则决定下一个状态状态状态 输入（激励）输入（激励）规则规则 状态迁移状态迁移20-为什么叫自动机？为什么叫自动机？n可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。n有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。21-自动机举例n例1：打电话(自动机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用四个状态来表示。q0q
12、0q1q1q2q2q3q3q4q4摘机摘机收到拨号音收到拨号音拨号拨号收应答信号收应答信号挂机挂机收齐号码收齐号码q0:q0:空闲状态空闲状态q1:q1:等待拨号状态等待拨号状态q2:q2:可以拨号状态可以拨号状态q3:q3:等待应答状态等待应答状态q4:q4:通话状态通话状态22-自动机举例n例2：串口通信 两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接连接请求q0q1q223-自动机举例n例3。在许多数字电子技术基础教科书中，串行序列检测电路设计常常被作为同步时序电路设计的一个例题。要求设计“111”序
13、列检测电路。它要求电路有一个串行输入端X 及一个串行输出端Z，当输入序列连续输入3个1时，输出为1，否则输出为0。24-25-自动机的分类n根据结构不同，自动机又可分为有限自动机，下推自动机，图灵机等。n下推自动机可以看作是由一条输入带，一个有限控制器和一个下推栈组成。n基本图灵机由一个具有读写头的有限控制器和一条无限带组成。n使用自动机，可以形式化的描述现实世界中的一些问题。26-3 3.3.3 形式语言与自动机的关系形式语言与自动机的关系n形式语言和自动机是密切相关的。形式语言 字符串自动机 字符串的识别系统n根据复杂程度可将形式语言分类，根据自动机的接受能力、处理能力的不同也将自动机分类
14、。二者之间具有较好的对应关系。27-3 3.3.3 形式语言与自动机的关系形式语言与自动机的关系28-语言与有限自动机（Finite Automata）设设 =0,1 ，L=w w 中至少有一个中至少有一个0 ，如如 0011,10,110111 L,而而11,1111 L。下图是一个可接受该语言的有限状态自动机下图是一个可接受该语言的有限状态自动机 12Start0,10129-小结n文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。n通过对一些定理的证明，说明对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。一定类型的自动
15、机和某种类型的文法具有等价性。30-课程内容及要求n课程内容：书上二、三、四、五、六章。n要求：通过本课学习，要求同学们掌握形式化描述方法，建立起形式语言与自动机的概念，并能在实际中加以应用。n通过对定理的证明，对同学们进行思维训练，并掌握一定的证明方法。31-证 明 技 术*定义、定理和证明定义、定理和证明基本证明方法基本证明方法 归纳证明技术归纳证明技术*引自清华大学计算机系软件技术研究所王生原老师课件引自清华大学计算机系软件技术研究所王生原老师课件32-定义、定理和证明n定义：对象和概念的描述。定义需要精确，明确说定义：对象和概念的描述。定义需要精确，明确说明对象的构成。明对象的构成。n
16、命题：描述某个对象所具有的某种命题：描述某个对象所具有的某种性质。性质。也需精确。也需精确。n证明：逻辑论证，确认一个命题为真。证明：逻辑论证，确认一个命题为真。n定理：被证明为真的（数学）命题。定理：被证明为真的（数学）命题。n引理：被证明的命题，有助于证明另一个更有意义引理：被证明的命题，有助于证明另一个更有意义的命题的命题33-演 绎 证 明 概念概念 一个一个 证明证明（proof）是命题的序列，是命题的序列，其中的每一个命题或者是已知的命题，或者是其中的每一个命题或者是已知的命题，或者是由前面出现过的命题使用逻辑公理和规则得出由前面出现过的命题使用逻辑公理和规则得出.已知的命题集合称
17、为已知的命题集合称为假设假设（hypothesis）或或前前提提（premise），），最后一个命最后一个命 题称为该前提的题称为该前提的结论结论（conclusion）.34-“If If Then Then”命题命题 证明方法证明方法 把把 If 部分作为已知的命题，把部分作为已知的命题，把 Then 部分作部分作为结论为结论.举例举例 如果如果x+y=1，那么那么x2-y2=x-y.证明证明:1 x2-y2 =(x+y)(x-y)/数学数学公理公理2 (x+y)=1 /已知已知x2-y2 =x-y /由由1、2 和算术性质推出和算术性质推出 35-“If-And-Only-If If-A
18、nd-Only-If”命题命题 欲证欲证 A if and only if B，可分别证明如下两个命题：可分别证明如下两个命题：1 if A then B，2 if B then A.36-有关集合的命题有关集合的命题 在本课程中，经常要证明两种不同方法构造的在本课程中，经常要证明两种不同方法构造的集合是相同的集合（比如语言表达的等价性）。集合是相同的集合（比如语言表达的等价性）。设设 R,S 为集合的表达式，下面两个命题的证明为集合的表达式，下面两个命题的证明需要参照集合的定义，分别表示为如下的命题。需要参照集合的定义，分别表示为如下的命题。欲证欲证 R S，可证明如下命题：可证明如下命题：
19、if x R then x S 欲证欲证 R=S，可分别证明如下两个命题：可分别证明如下两个命题：1 if x R then x S 2 if x S then x R37-原命题的逆否命题原命题的逆否命题有时，证明原命题的逆否有时，证明原命题的逆否(contrapositive)命题更加方便命题更加方便.欲证欲证 if A then B，可证明如下命题：可证明如下命题：if not B then not A原因：两个命题是等价，原因：两个命题是等价，（蕴涵逻辑等价）。（蕴涵逻辑等价）。38-反证法反证法 反证（反证（proof by contradiction）欲证欲证 if H then
20、C，可以把可以把 H 和和 not C 都作为已知的命题，把任何一个矛盾都作为已知的命题，把任何一个矛盾(contradiction)命题作为新的结论命题作为新的结论.39-举例证明或否证举例证明或否证 举例证明存在量化的命题举例证明存在量化的命题 如命题：存在整数如命题：存在整数 a，满足满足 a2=2a.证明证明:取取 a=2.，满足满足 a2=2a.举反例否定全称量化的命题举反例否定全称量化的命题 如命题：所有整数如命题：所有整数 a，都满足都满足 a2=2a.否证否证:取取 a=1.，不满足不满足 a2=2a.40-归纳证明在处理递归定义的对象时归纳证明在处理递归定义的对象时“必不可少
21、必不可少”。在自动机理论中，需要归纳证明处理递归定义的概在自动机理论中，需要归纳证明处理递归定义的概念，比如：树、表达式等。念，比如：树、表达式等。归纳法原理：归纳法原理：如果证明了如果证明了S(i),并且证明了对所有并且证明了对所有ni，S(n)蕴涵蕴涵S(n+1)，就可得出：对所有，就可得出：对所有ni,S(n)成立。成立。归纳证明与递归定义的对应。归纳证明与递归定义的对应。归 纳 证 明 与 结 构 归 纳 法41-归 纳 证 明 与 结 构 归 纳 法集合的递归定义集合的递归定义 由由 3 部分构成：部分构成：1 基础基础（basis）/直接定义集合中的元素（至少直接定义集合中的元素（
22、至少1个）个）2 归纳归纳（induction）/从已知元素生成新元素的规则从已知元素生成新元素的规则 3 极小性限制极小性限制 /申明集合中的元素只能由申明集合中的元素只能由 1、2 生成生成 42-归 纳 证 明 与 结 构 归 纳 法结构归纳法结构归纳法 对于归纳（递归）定义的集合对于归纳（递归）定义的集合 S，欲证对于任意欲证对于任意x S，满足性质满足性质P(x).1 基础基础（basis）/若有直接定义若有直接定义 a S，则证明则证明 P(a)2 归纳归纳（induction）/若归纳定义中有规则若归纳定义中有规则 if a1,a2,an S then f(a1,a2,an)S，
23、则证明则证明 if P(a1),P(a2),P(an)S then P(f(a1,a2,an)43-归纳定义归纳定义合法括号串的集合合法括号串的集合 S 1 基础基础 空串空串 S 2 归纳归纳 若若 x S，则则(x)S；若若 x,y S，则则 xy S.3 极小性限制极小性限制 S 中的元素只能由中的元素只能由 1、2 生成生成 (或：或：S是满足是满足1、2的最小集合的最小集合)命题：合法括号串集合命题：合法括号串集合 S 中每个括号串的中每个括号串的“(”与与“)”数目相数目相等等 证明证明:1 基础基础 空串空串 的的“(”与与“)”数目相等，都为数目相等，都为0；2 归纳归纳 设设
24、 x,y 的的“(”与与“)”数目相等，前者为数目相等，前者为m，后者为后者为n；(x)的的“(”与与“)”数目都为数目都为m+1；xy 的的“(”与与“)”数目都为数目都为m+n.归纳定义与结构归纳证明（例）归纳定义与结构归纳证明（例）44-自然数自然数 自然数集合自然数集合N是满足如下条件的最小集合：是满足如下条件的最小集合：(1)0 N;(2)若若 n N,则则n的后继的后继n+1 N 数学归纳法数学归纳法 欲证对任意自然数欲证对任意自然数n，P(n)成立，成立，(1)先证先证 P(0)成立;(2)再证若 P(n)成立,则P(n+1)成立 另一种形式另一种形式 (1)先证先证P(0)成立
25、成立;(2)再证若对任意再证若对任意kn，P(k)成立成立,则则P(n)成立成立 对任何良序集合，都可以有这两种形式对任何良序集合，都可以有这两种形式基于自然数的归纳基于自然数的归纳 一般数学归纳法一般数学归纳法45-第二章第二章 语言及文法语言及文法n主要内容主要内容：n定义形式语言的术语定义形式语言的术语n给出文法的定义和文法的分类给出文法的定义和文法的分类n要求掌握：要求掌握：n语言和文法的形式定义语言和文法的形式定义nCHOMSKY文法体系的分类。文法体系的分类。46-第一节第一节 语言的定义与运算语言的定义与运算一、一、语言的一些术语：语言的一些术语：n 字母表：字母表：字符的有限集
26、合，记为字符的有限集合，记为T。n字符串：字符串：由字母表由字母表T中的字符构成的序中的字符构成的序列称字母表列称字母表T上的字符串（句子）。上的字符串（句子）。n 常记为常记为u,v,w,x,y,z；n 常用常用a,b,c,d 标识单个字符。标识单个字符。47-字字 母母 表表 （AlphabetAlphabet）概念概念 形式符号的集合形式符号的集合 记号记号 常用常用 T、表示表示 举例举例-英文字母表英文字母表 a,b,z,A,B,Z -英文标点符号表英文标点符号表 ,;:.?!“”()-汉字表汉字表 ,自自,动动,机机,-化学元素表化学元素表 H,He,Li,-T=a,n,y,任任,
27、意意 48-字字 符符 串串 （stringstring）概念概念 字母表字母表 T 上的一个上的一个字符串字符串（简称（简称串串），或称为），或称为 字字（word），），为为 T 中字符构成的一个有限序列。中字符构成的一个有限序列。空串空串（empty string）,用用 表示，不包含任何表示，不包含任何 字符。字符。举例举例 设设 T=a,b ，则则 ,a,ba,bbaba 等都是串等都是串 字符串字符串 w 的的长度长度，记为，记为 w ，是包含在是包含在 w 中字符的个中字符的个数数 举例举例 =0，bbaba =5 ai 表示含有表示含有i个个a的字符串的字符串 49-连接（连接
28、（concatenation）设设 x,y为串为串,且且 x a1a2 am,y b1b2 bn,则则 x 与与 y 的连接的连接 x y a1a2 am b1b2 bn 连接运算的性质连接运算的性质 -(x y)z x（y z）-x x x-x y x+y 关关 于于 字字 符符 串串 的的 运运 算算50-其它其它 如如 取头字符取头字符，取尾部取尾部，子串匹配子串匹配 等等n 设设1,2,3是字母表是字母表T上的字符串，称：上的字符串，称：n1是字符串是字符串12的的前缀前缀，n2是字符串是字符串12的的后缀后缀，n2是字符串是字符串123的的子串子串。n 空串是任何字符串的前缀，后缀及
29、子串。空串是任何字符串的前缀，后缀及子串。n 例例：abc的前缀的前缀 a ab abc.后缀后缀 c bc abc.子串子串 a b c ab bc abc ,即一个字符串可以看作是多个字符串的连接。即一个字符串可以看作是多个字符串的连接。关关 于于 字字 符符 串串 的的 运运 算算51-n 字符串字符串的逆用的逆用 表示。表示。是字符是字符串串的倒置。的倒置。=b1b2bn =bnbn-1b2b1n 空串空串的逆还是的逆还是52-字字 母母 表表 的的 幂幂 运运 算算 幂运算幂运算 Tn 用来表示用来表示 该字母表长度为该字母表长度为n的所有串的集的所有串的集合。设合。设 T 为字母表
30、，为字母表，n 为任意自然数，为任意自然数，定义（定义（1）T0=（2）设）设 x Tn-1，a T，则则a x Tn （3）Tn 中的元素只能由（中的元素只能由（1）和）和（2）生成）生成 闭包闭包 T*=T0 T1 T2 闭包闭包 T+=T1 T2 T3 T*=T+，T+=T*-53-闭包的物理意义闭包的物理意义 T的星号闭包的星号闭包T*：字母表T上的所有字符串和空串的集合。T的正闭包的正闭包T+：字母表T上的所有字符串构成的集合。T*=T+举例举例 设设 T=0，1 ，则则 T0=，T1=0，1 ，T2=00，01，10，11 ，T*=，0，1，00，01，10，11，T+=0，1，0
31、0，01，10，11，54-语 言（Languages）概念概念 设设 T 为字母表，则任何集合为字母表，则任何集合 L T*是是字母字母表表T上的上的一个语言（一个语言（language）举例举例 -英文单词集英文单词集 ,English,words,-C 语言程序集语言程序集 字母表？字母表？-汉语成语集汉语成语集 ,马到成功马到成功,-化学分子式集化学分子式集 ,H2O,NaCl,-any,任意任意 55-语 言（Languages）举例举例：设：设T=a，b 则则 L1 =anbn|n1 L3=bk|k 是质数是质数 L2 =只有一个空句子的语言只有一个空句子的语言 L4=空语言空语言
32、 均为字母表均为字母表T上的语言。上的语言。由语言的定义知语言是集合，对于集合的运算可应由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。用于对于语言的计算。如并，交，补，差。56-语言的基本运算 语言的积：语言的积：两个语言L1 和L2的积L1 L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。设T=a,b，L1和 L2是T上的语言。L1=ab,ba L2=aa,bb则 L1 L2=abaa,abbb,baaa,babb L2 L1=aaab,aaba,bbab,bbban L1 L2 L2 L1 语言
33、的积不可交换。语言的积不可交换。57-语言的基本运算 语言的幂：语言的幂：语言的幂可归纳定义如下语言的幂可归纳定义如下:L0=Ln=L Ln-1=Ln-1 L n 1上例中，上例中，L12=abab,abba,baab,baba L22=aaaa,aabb,bbaa,bbbb 58-第二节 文法n定义：所谓文法是用来定义语言的一个数学模型：所谓文法是用来定义语言的一个数学模型n表示语言的方法：n若语言若语言L是有限集合，可用是有限集合，可用列举法n若若L是无限集合（集合中的每个元素有限长度），是无限集合（集合中的每个元素有限长度），用其他方法。用其他方法。n方法一：文法产生系统，由定义的文法规
34、则产方法一：文法产生系统，由定义的文法规则产生出语言的每个句子生出语言的每个句子n方法二：机器识别系统：当一个字符串能被一方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语个语言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语言。言的一个句子，否则不属于该语言。59-元语言元语言n定义定义：描述语言的语言描述语言的语言例如：各种各样的程序设计语言例如：各种各样的程序设计语言n当人们要解释或讨论程序设计语言本身时，又需要当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语言，即某种程一种语言，被讨论的语言叫做对象语言，即某种程序
35、设计语言，讨论对象语言的语言称为元语言序设计语言，讨论对象语言的语言称为元语言。60-BNFBNF（巴科斯范式）巴科斯范式）BNF范式通常被作为讨论某种程序设计语言语法的元语言n:=0|1|2|9 :=“定义为”n:=A|B|C|Z|a|b|z :=|.n通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。nBNF定义了一种语言，其中标识符如上定义。nBNF描述它所定义的语言，为元语言。61-n例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。如他是学生。n文法是一种元语言，
36、一种方法，根据文法产文法是一种元语言，一种方法，根据文法产生出语言的句子。生出语言的句子。62-三、Chomsky文法体系n例如：BNF:=:=:=:=a|b|z|A|B|Z :=0|1|9将:=改为表示可被代替用I,L,D分别表示标识符、字母、数字;63-三、Chomsky文法体系则上述表达式可以表示为则上述表达式可以表示为 IL IIL IID La|b|.|z D0|1|.9这就是一个文法的生成式集合。这就是一个文法的生成式集合。64-三、Chomsky文法体系nChomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集
37、合P（生成式集合），一个起始符S。nP中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而推导出来。n可见文法的核心是生成式的集合，它决定了语言中句子的产生。65-文法的形式定义n文法G是一个四元组G=(N，T，P，S)，其中N 非终结符的有限集合T 终结符的有限集合 NT=P 形式为的生成式的有限集合。且(NT)*N+(NT)*(NT)*S 起始符 且S N。66-n将上例用文法表示G=(N，T，P，S)N=I,L,DT=a,b,c,z,0,1,9P=I,La,D0,D9S=I n文法是语言的产生系统，研究怎样构造文法
38、能产生出符合要求的句子。67-四推导与句型1、直接推导设G=（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，则有A=称A直接推导出，或说是A的直接推导。68-n设G=(N,T,P,S)是文法，、0、1n、都是（NT）*中的字符串，且=0、=n，其中i直接推导出i+1（0in）,则称序列0=1=2=n是长度为n的推导序列，而=0是长度为0的推导序列。n对推导出记为 ，若推导序列长度大于0，则记为 。n推导序列的每一步，都产生一个字符串，这些字符串一般称为句型。2、推导序列*G G 69-3、句型和句子n句型字符串字符串是文法是文法G的句型，当且仅当的句型，当且仅当S ，且
39、且（NT）*。n 句子是是G的句子，当且仅当的句子，当且仅当S ,且且T*。（。（是由是由终结符组成的字符串）终结符组成的字符串）例：例：I=L=a I=IL=LL=zL=zbn句型包含句子*G*G 70-4文法产生的语言由文法由文法G产生的语言记为产生的语言记为L(G)。L(G)=|T*且且S 或：或：L(G)中的一个字符串，必是由终结符中的一个字符串，必是由终结符组成的，并且是从起始符组成的，并且是从起始符S推导出来的。推导出来的。*G 71-第三节 Chomsky文法体系分类n文法文法 G=(N,T,P,S)；P:其中其中（NT）*N+（NT）*（NT）*属于属于Chomsky文法体系文
40、法体系n该体系对该体系对生成式生成式的形式做了一些规定，分的形式做了一些规定，分为四类，即为四类，即0型、型、1型、型、2型、型、3型文法型文法n0型文法：无限制文法型文法：无限制文法对应的语言：递归可枚举语言，与图灵机等价。72-1型文法n也称上下文有关文法（也称上下文有关文法（CSG：Context-sensitive Grammar)生成式的形式为生成式的形式为，其中其中|，（NT）+，（NT）*N+（NT）*n对应的语言：上下文有关语言（对应的语言：上下文有关语言（CSL：Context-sensitive Language)n若不考虑若不考虑，与线性有界自动机（与线性有界自动机（LB
41、A,Linear Bounded Automaton）等价。等价。73-1型文法语言限定约束：n左部的长度小于右部左部的长度小于右部n不含不含A-A-上下文有关语言CSL是对实际程序语言结构的抽象：典型的这类语言结构包括：变量的声明与引用、变量的声明与引用、过程调用时形参与实参的一致性检查等。过程调用时形参与实参的一致性检查等。74-2型文法n也称上下文无关文法（也称上下文无关文法（CFG：Context-free Grammar)A,AN,且且（NT）*n对应的语言：上下文无关语言对应的语言：上下文无关语言（CFL：Context-free Language)。n对 应 的 自 动 机：下
42、推 自 动 机（对 应 的 自 动 机：下 推 自 动 机（P D A：Pushdown Automaton)。75-n语言限定约束：语言限定约束：n左部是1个非终结符。nCFL对实际语言结构的抽象：对实际语言结构的抽象：n表示句子的语法结构，如：表达式，嵌套结构。1.目前的程序设计语言主要采用CFL描述语法结构。76-3型文法也称正则文法也称正则文法n右线性文法（右线性文法（Right-linear Grammar）：）：AB 或或 AA、BN,T*。n左线性文法（左线性文法（Left-linear Grammar）：）：AB或或 AA、BN,T*。n对应的语言：正则语言对应的语言：正则语言
43、n对 应 的 自 动 机：有 限 自 动 机（对 应 的 自 动 机：有 限 自 动 机（F i n i t e Automaton）。）。77-文法举例文法举例例例1：G=(A,B,C,a,b,d,P,A)P:AAB；ABCAAB；Ad；Ba；Cb 是是1型文法。型文法。A=dA=AB=dB=daA=AB=ABB=dBB=daB=daaA=AB=CAAB=bAAB=bdAB=bdCAAB=bdbAAB=bdbdAB=bdbddB=bdbdda78-文法举例文法举例例例2：G=(A,B,C,a,b,c,P,A)P:Aabc AaBbc BbbB BcCbcc bCCb aCaaB aCaa 是
44、是1型文法。型文法。其定义的其定义的 L=anbncn|n1n A=abcn A=aBbc=abBc=abCbcc=aCbbcc=aabbcc 79-文法举例文法举例例例3：G=(S,B,C,a,b,P,A)P:SaC；SbB；BaS；BbBB Ba；CbS；CaCC；Cb 是是2型文法型文法 n S=aC=ab nS=aC=aaCCnS=aC=abS=abaC=ababS=ababaC=abababnS=bB=bbBB=bbaSB=bbaaCB=bbaabB=bbaaba80-文法举例文法举例例例4：G=(A,B,C,a,b,c,P,A)P:ABa；Ac；BCb；Ccn左线性文法左线性文法n L=c,cba 正则语言正则语言n注意：已知语言求文法，文法不是唯一的，即可以注意：已知语言求文法，文法不是唯一的，即可以有不同的表达方法有不同的表达方法。81-四类文法之间的关系n只是对生成式形式加以限制只是对生成式形式加以限制n0型型 无限制无限制n1型型 不允许不允许A形式形式n2型型n3型型 属于属于2型型n不含不含A的的2型、型、3型属于型属于1型，型，1型、型、2型、型、3型均属于型均属于0型。型。82-n作业：作业：P47 4,6,7 题题
