《计算引论4文法与语言》由会员分享，可在线阅读，更多相关《计算引论4文法与语言（43页珍藏版）》请在金锄头文库上搜索。
1、计算引论第三章 文法与语语言n求解问题问题 与 识别语识别语 言n问题问题 抽象为为符号串的集合；n符号串称为为句子，问题问题 是句子的集合；求解问题问题 抽象为识别语为识别语 言。n问题问题 提出: 如何构造可以接受及产产生一个语语言的计计算模型?n语语言识别识别 器: 对对一个已经经存在的字符串集合, 如何判断它就是符合条件的语语言? 解决接受的问题问题 。n语语言产产生器: 怎样产样产 生一个语语言？ 解决产产生的问题问题 。n语言的识别问题：要让计算机自动识别语言（自然语言或机器语言或程序设计语言），必须先用形式化的方法来表示语言。n文法能清晰描述语语言的语语法构成,。n文法能自动动构
2、造有效的语语言识别识别 器。n文法G定义为义为 四元组组(V,T,S,P)，其中V 是有限的非终终极符集合； T 是有限的终终极符集合；S 是开始符，ST。必须须在某个产产生式的左边边 出现现一次；P 是产产生式的集合，且具有下面的形式： ，其中，(V T )*n非终极符号表示语法概念（如主、谓、宾等）或语法范畴。n终极符号表示语言的基本符号，例如26个字母（大、小写）及标点符号等。nS是非终极符中的一个语法概念，是最关心的语法概念。nP是语法规则，例如：句子定义为 主语谓语宾语 或句子定义为 主语系词表语称为产生式，即由主语谓语宾语可以产生句子n产生式表示一条语法规则，P为产生式集合。n文法
3、分类类：A,BV，aT。对对文法中的产产生式： nO型文法: 短语语文法。中至少含一个非终终极符。n1型文法: 上下文有关文法。它是0型文法的特例，要求|(S例外，S不得出现现于产产生式右部)。n2型文法: 上下文无关文法。它是1型文法的特例，要求产产生式左部是一个非终终极符: A 。n3型文法: 正则则文法。它是2型文法的特例，要求产产生式具有下面形式之一: Aa ，AaB。文法的乔姆斯基体系正则文法上下文无关文法上下文有关文法短语文法n相关定义义n定义义 (字符串)：设设A是基本符号表（字母表），A=a1, a2, , an，则则A上字符串集合表示为为：A*=A0 A1 A2 Ak A+=
4、A1 A2 Ak 其中：Ai是长长度为为i的字符串。 A* = A0 A+n推导导：如果A是一个产产生式，则对则对 字符串A，有A , 表示一步推导导(用A )。n +:表示通过过一步或多步可推导导出n *:表示通过过0步或多步可推导导出n句型：如果有S* ，则则称符号串为为相应应文 法的句型，其中S是文法的开始符。 n句子：如果只包含终终极符，则则称为为相应应文 法的句子。 n语语言：L(G)= u| S + u ,u T*。文法G所定义义的语语言是其开始符所能推导导的所 有终终极符号串(句子)的集合。n例：某语语言有文法G：字母数学标识标识 符，尖括号指非终终极符。终终极符T：0, 1,
5、2, , 9, a, b, , z, A, B, , Z, _。P中的产产生式有：数字 0 数字 1 数字 9 字母 a字母 b字母 zn标识符可以形式化地表示为：标识符 字母标识符 标识符字母标识符 标识符数字n例：G=(A, B, C, S, a, b, P, S),其中：P中的产产生式集合为为：nS AB , S BCnB CC , B bnC AB , C anA BA , A an试证明给定串baabaT*，且S baaba，即是否可以由文法规则推导出该串。证明：因为baaba串中的每一个字符均属于T，故baabaT*S BC bC bAB baB baCC baCa baABa b
6、aaBa baaba.3.2 正则语言的识别n正则则文法定义义：G(V, T, P, S), P中的产产生式形如Aa, 或 AaB,aT,A,BV。 n右范式：形如AaB称为为右范式，其中非终终极 符于终终极符的右边边。n左范式：形如ABa称为为左范式，其中非终终极 符于终终极符的左边边。 n正则语则语 言 正则则文法G生成的语语言：L(G) = |T*且S +n正则语则语 言的识别识别对对文法S，任给给串T*，S +成立否 。n识别识别 步骤骤：任给给串T*，S +成立否。n任给给串，中所有的元素是否为给为给 定终终极 符集中的元素构成。n可否由非终终极符中的S经过经过 多步推导导得到串 。
7、 n识别识别 算法：设设：=a1an,aiT。n若n=1，问题问题 等价于检查检查 Sa1P？n若n2，则则需要证证明S a1B1 + a1a2an ，问题变为问题变为 ：B1 + a2an是否成立。递递推下 去， B1 a2B2 ？ + a2anB2 a3B3 ？+a3an Bn-1 an？ 即检查检查 上述表达式是否均在文法集合P中。 n正则则运算：设设A和B是两个正则语则语 言，n并：A B x | xA 或x B n连连接：A B = xy| xA 且yB n星号*：A* = x1xk|k0且xiAi n定理1：正则语则语 言在正则则运算下封闭闭。即：如果A和B是正则语则语 言，则则A
8、B, AB, A*也是正则语则语 言。 3.3 有限自动机n有限自动动机的结结构abababab有限控制器q0q5q4 q3q1q2输入带读头特点: 1.以字符串作为输为输 入, 通过输过输 入带传带传 送字符串;2.除了提示输输入的字符串是否接受外, 没有任何其它的输输出;3.它的固定中央处处理器完全没有记忆记忆 功能;4.类类似一个语语言识别识别 器.n组组成:n输输入带带: 放字符串的装置n有限控制器: 含不同的内部状态态n读头读头n原理:在一定的时间间时间间 隔内, 自动动机根据从输输入带带 上读读入的符号和当前的内部状态态, 进进入一个 新的状态态.过过程:n读读取一个符号后, 读读
9、写头头向右移动动一个方格, 读读取 下一个符号, 有限控制器的内部状态发态发 生改变变. 最 终读终读 写头头到达输输入串的尽头头.n自动动机将根据它所处处的状态态来说说明它是否接受读读 入的字符串, 如果此时时的状态态正好是一个终终止状 态态, 则认为该则认为该 字符串是可接受的.n根据每次转换转换 后的状态态是否唯一, 可将有限自动动机分为为确定有限自动动机和非确定有限自动动机。n确定有限自动动机DFA: 为为一个五元组组M=(Q, , q0, F), 其中nQ为为状态态的有限集合n为为有限字母表nq0Q为为起始状态态nF Q为终为终 止状态态集n：QQ是转换转换 函数n格局: 机器的状态
10、态(有限控制器, 读读写头头和输输入带带)的表示方式.由当前状态态和字符串未输输入部分决定, 属于Q* 。n例如：（q2,ababab）n连续时连续时 刻的格局序列就是自动动机在输输入字符串上的计计算(computation).n若自动动机M的一个格局经过经过 一步(读读写头头)移动动到达另一个格局, 则则称这这两个格局之间间有二元关系M.n例如, 若(q,w)和(q, w)为为M的格局, (q, w)M(q,w) iff对对某a有w=aw及(q,a)=q此时时称(q,w)一步产产生(q,w).n*M ：M的自反传递闭传递闭 包n如(q, w)*M (q, w)，表示(q, w)经过经过 多步
11、(包括 0步) 产产生 (q, w).n字符串w*被M=(Q, , q0, F)接受,当且仅仅当 存在状态态qF, 使得(q0, w)*M (q, ).n所有由被M接受的字符串组组成的集合即为为M接受 的语语言, 记为记为 L(M).n有限自动动机的表示：n 状态图态图n 状态态表n例, 令M为为确定有限自动动机(Q, , , q0, F), 其中Q=q0,q1, =a, b, F=q0, 为为如右表所示qw(q, w)q0aq0q0bq1q1aq1q1bq0an状态图态图状态态用结结点表示, 用标标有a的从q指向q的箭头头表 示(q,a)=q, 终终止状态态用双圆圆圈表示, 起始状态态用 表
12、示q0bbq1an若输输入为为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接受。n非确定有限自动动机NFA: 为为一个五元组组 M=(Q, , Q0, F), 其中nQ为为状态态的有限集合n为为有限字母表nQ0 Q为为起始状态态集nF Q为终为终 止状态态集n:Q(Q)是转换转换 函数n 例NFAq0q1q2q30,10,110,1n定义义：对对两台自动动机M1，M2，如果L(M1) = L(M2)，则则称M1和M2等价。n 定理2：每一台非确定有限自动动机都等价于某一台确定有限自动动机。定理3：语语言是正则则的，当且仅仅当它可以被有限自动动机接受。n正则语则语 言的描述局限n不能描述配对对或嵌套结结构n例 BEGINENDn不能描述重复串n例wcw | w是由a和b组组成的串结结构
