计算引论4文法与语言.ppt

1、计算引论,第三章 文法与语言,求解问题 与 识别语言 问题抽象为符号串的集合； 符号串称为句子，问题是句子的集合； 求解问题抽象为识别语言。,问题提出: 如何构造可以接受及产生一个语言的计算模型? 语言识别器: 对一个已经存在的字符串集合, 如何判断它就是符合条件的语言? 解决接受的问题。 语言产生器: 怎样产生一个语言？ 解决产生的问题。,语言的识别问题： 要让计算机自动识别语言（自然语言或机器语言或程序设计语言），必须先用形式化的方法来表示语言。 文法能清晰描述语言的语法构成,。 文法能自动构造有效的语言识别器。,文法G定义为四元组(V,T,S,P)，其中 V 是有限的非终极符集合； T

2、是有限的终极符集合； S 是开始符，ST。必须在某个产生式的左边出现一次； P 是产生式的集合，且具有下面的形式： ，其中，(V T )*,非终极符号表示语法概念（如主、谓、宾等）或语法范畴。 终极符号表示语言的基本符号，例如26个字母（大、小写）及标点符号等。 S是非终极符中的一个语法概念，是最关心的语法概念。,P是语法规则，例如： 句子定义为 主语谓语宾语 或 句子定义为 主语系词表语 称为产生式，即由主语谓语宾语可以产生句子 产生式表示一条语法规则，P为产生式集合。,文法分类： A,BV，aT。对文法中的产生式： O型文法: 短语文法。中至少含一个非终极符。 1型文法: 上下文有关文法。

3、它是0型文法的特例，要求|(S例外，S不得出现于产生式右部)。 2型文法: 上下文无关文法。它是1型文法的特例，要求产生式左部是一个非终极符: A 。 3型文法: 正则文法。它是2型文法的特例，要求产生式具有下面形式之一: Aa ，AaB。,相关定义 定义 (字符串)：设A是基本符号表（字母表），A=a1, a2, , an，则A上字符串集合表示为： A*=A0 A1 A2 Ak A+=A1 A2 Ak 其中：Ai是长度为i的字符串。 A* = A0 A+,推导：如果A是一个产生式，则对字符串A，有A , 表示一步推导(用A )。 +:表示通过一步或多步可推导出 *:表示通过0步或多步可推导出

4、,句型：如果有S* ，则称符号串为相应文法的句型，其中S是文法的开始符。 句子：如果只包含终极符，则称为相应文法的句子。 语言： L(G)= u| S + u ,u T*。 文法G所定义的语言是其开始符所能推导的所有终极符号串(句子)的集合。,例：某语言有文法G：字母数学标识符，尖括号指非终极符。终极符T：0, 1, 2, , 9, a, b, , z, A, B, , Z, _。P中的产生式有：,数字 0 数字 1 数字 9 字母 a 字母 b 字母 z,标识符可以形式化地表示为： 标识符 字母 标识符 标识符字母 标识符 标识符数字,例：G=(A, B, C, S, a, b, P, S)

5、,其中：P中的产生式集合为： S AB , S BC B CC , B b C AB , C a A BA , A a,试证明给定串baabaT*，且S baaba，即是否可以由文法规则推导出该串。,证明：因为baaba串中的每一个字符均属于T，故baabaT* S BC bC bAB baB baCC baCa baABa baaBa baaba.,3.2 正则语言的识别,正则文法定义： G(V, T, P, S), P中的产生式形如Aa, 或AaB,aT,A,BV。 右范式：形如AaB称为右范式，其中非终极符于终极符的右边。 左范式：形如ABa称为左范式，其中非终极符于终极符的左边。,正则

6、语言 正则文法G生成的语言： L(G) = |T*且S + 正则语言的识别 对文法S，任给串T*，S +成立否。,识别步骤： 任给串T*，S +成立否。 任给串，中所有的元素是否为给定终极符集中的元素构成。 可否由非终极符中的S经过多步推导得到串。,识别算法：设：=a1an,aiT。 若n=1，问题等价于检查Sa1P？ 若n2，则需要证明 S a1B1 + a1a2an ， 问题变为：B1 + a2an是否成立。递推下去， B1 a2B2 ？ + a2an B2 a3B3 ？+ a3an Bn-1 an？ 即检查上述表达式是否均在文法集合P中。,正则运算：设A和B是两个正则语言， 并：A B

7、x | xA 或x B 连接：A B = xy| xA 且yB 星号*：A* = x1xk|k0且xiAi ,定理1： 正则语言在正则运算下封闭。 即： 如果A和B是正则语言，则AB, AB, A*也是正则语言。,3.3 有限自动机,有限自动机的结构,a,b,a,b,a,b,a,b,有限控制器,q0,q5,q4,q3,q1,q2,输入带,读头,特点: 以字符串作为输入, 通过输入带传送字符串; 除了提示输入的字符串是否接受外, 没有任何其它的输出; 它的固定中央处理器完全没有记忆功能; 类似一个语言识别器.,组成: 输入带: 放字符串的装置 有限控制器: 含不同的内部状态 读头 原理: 在一定

8、的时间间隔内, 自动机根据从输入带上读入的符号和当前的内部状态, 进入一个新的状态.,过程: 读取一个符号后, 读写头向右移动一个方格, 读取下一个符号, 有限控制器的内部状态发生改变. 最终读写头到达输入串的尽头. 自动机将根据它所处的状态来说明它是否接受读入的字符串, 如果此时的状态正好是一个终止状态, 则认为该字符串是可接受的.,根据每次转换后的状态是否唯一, 可将有限自动机分为确定有限自动机和非确定有限自动机。,确定有限自动机DFA: 为一个五元组 M=(Q, , q0, F), 其中 Q为状态的有限集合 为有限字母表 q0Q为起始状态 F Q为终止状态集 ：QQ是转换函数,格局: 机

9、器的状态(有限控制器, 读写头和输入带)的表示方式.由当前状态和字符串未输入部分决定, 属于Q* 。 例如：（q2,ababab） 连续时刻的格局序列就是自动机在输入字符串上的计算(computation).,若自动机M的一个格局经过一步(读写头)移动到达另一个格局, 则称这两个格局之间有二元关系M. 例如, 若(q,w)和(q, w)为M的格局, (q, w)M(q,w) iff 对某a有w=aw及(q,a)=q 此时称(q,w)一步产生(q,w).,*M ：M的自反传递闭包 如(q, w)*M (q, w)，表示(q, w)经过多步(包括0步) 产生 (q, w). 字符串w*被M=(Q,

10、 , q0, F)接受,当且仅当存在状态qF, 使得(q0, w)*M (q, ). 所有由被M接受的字符串组成的集合即为M接受的语言, 记为L(M).,有限自动机的表示： 状态图 状态表,例, 令M为确定有限自动机(Q, , , q0, F), 其中Q=q0,q1, =a, b, F=q0, 为如右表所示,a,状态图 状态用结点表示, 用标有a的从q指向q的箭头表示(q,a)=q, 终止状态用双圆圈表示, 起始状态用表示,q0,b,b,q1,a,若输入为aabba, M的初始格局为(q0, aabba)则有 (q0,aabba) M(q0, abba) M(q0, bba) M(q1, ba) M(q0, a) M(q0, ) 即(q0, aabba)*M(q0, ),因此aabba被M接受。,非确定有限自动机NFA: 为一个五元组 M=(Q, , Q0, F), 其中 Q为状态的有限集合 为有限字母表 Q0 Q为起始状态集 F Q为终止状态集 :Q(Q)是转换函数,例NFA,