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

格局: 机器的状态(有限控制器, 读写头和输入带)的表示方式.由当前状态和字符串未输入部分决定, 属于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, ∑,??, q0, F)接受,当且仅当存在状态q∈F, 使得(q0, w)?*M (q, ?). 所有由被M接受的字符串组成的集合即为M接受的语言, 记为L(M). 有限自动机的表示： 状态图 状态表 例, 令M为确定有限自动机(Q, ?, ?, q0, F), 其中Q={q0,q1}, ?={a, b}, F={q0}, ?为如右表所示 q w ?(q, w) q0 a q0 q0 b q1 q1 a q1 q1 b 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 q0 q1 q2 q3 0,1 0,1 1 0,? 1 定义： 对两台自动机M1，M2，如果L(M1) = L(M2)，则称M1和M2等价。 定理2： 每一台非确定有限自动机都等价于某一台确定有限自动机。 定理3： 语言是正则的，当且仅当它可以被有限自动机接受。 正则语言的描述局限 不能描述配对或嵌套结构 例 {{…}} BEGIN…END 不能描述重复串 例{wcw | w是由a和b组成的串结构} 计算引论 第三章 文法与语言 求解问题 与 识别语言 问题抽象为符号串的集合； 符号串称为句子，问题是句子的集合； 求解问题抽象为识别语言。 问题提出: 如何构造可以接受及产生一个语言的计算模型? 语言识别器: 对一个已经存在的字符串集合, 如何判断它就是符合条件的语言? 解决接受的问题。 语言产生器: 怎样产生一个语言？ 解决产生的问题。 语言的识别问题： 要让计算机自动识别语言（自然语言或机器语言或程序设计语言），必须先用形式化的方法来表示语言。 文法能清晰描述语言的语法构成,。 文法能自动构造有效的语言识别器。 文法G定义为四元组(V,T,S,P)，其中 V 是有限的非终极符集合； T 是有限的终极符集合； S 是开始符，S?T。必须在某个产生式的左边出现一次； P 是产生式的集合，且具有下面的形式： ? ? ?，其中?，??(V ? T )* 非终极符号表示语法概念（如主、谓、宾等）或语法范畴。 终极符号表示语言的基本符号，例如26个字母（大、小写）及标点符号等。 S是非终极符中的一个语法概念，是最关心的语法概念。 P是语法规则，例如： ＜句子＞定义为 ＜主语＞＜谓语＞＜宾语＞ 或 ＜句子＞定义为 ＜主语＞＜系词＞＜表语＞ 称为产生式，即由＜主语＞＜谓语＞＜宾语＞可以产生＜句子＞ 产生式表示一条语法规则，P为产生式集合。 文法分类： A,B?V，a?T。对文法中的产生式?→?： O型文法: 短语文法。?中至少含一个非终极符。 1型文法: 上下文有关文法。它是0型文法的特例，要求|?|?|?|(S→?例外，S不得出现于产生式右部)。 2型文法: 上下文无关文法。它是1型文法的特例，要求产生式左部是一个非终极符: A→? 。 3型文法: 正则文法。它是2型文法的特例，要求产生式具有下面形式之一: A→a ，A→aB。 文法的