北航 计算理论 第三章 文法与语言

1、计算理论计算理论 第三章第三章 文法与语言文法与语言 n求解问题求解问题 与与 识别语言识别语言 n问题抽象为符号串的集合；问题抽象为符号串的集合； n符号串称为句子，问题是句子的集合；符号串称为句子，问题是句子的集合； 求解问题抽象为识别语言求解问题抽象为识别语言。 n问题提出问题提出: 如何构造可以接受及产生一个语言如何构造可以接受及产生一个语言 的计算模型的计算模型? n语言识别器语言识别器: 对一个已经存在的字符串集合对一个已经存在的字符串集合, 如何判断它就是符合条件的语言如何判断它就是符合条件的语言? 解决接受的解决接受的 问题。问题。 n语言产生器语言产生器: 怎样产生一个语言？

2、怎样产生一个语言？ 解决产生的解决产生的 问题。问题。 n语言的识别问题：语言的识别问题： 要让计算机自动识别语言（自然语言或要让计算机自动识别语言（自然语言或 机器语言或程序设计语言），必须先用机器语言或程序设计语言），必须先用 形式化的方法来表示语言。形式化的方法来表示语言。 n文法能清晰描述语言的语法构成文法能清晰描述语言的语法构成,。 n文法能自动构造有效的语言识别器。文法能自动构造有效的语言识别器。 n文法文法G定义为四元组定义为四元组(V,T,S,P)，其中，其中 V 是有限的非终极符集合；是有限的非终极符集合； T 是有限的终极符集合；是有限的终极符集合； S 是开始符，是开始符

3、，S T。必须在某个产生式的左边。必须在某个产生式的左边 出现一次；出现一次； P 是产生式的集合，且具有下面的形式：是产生式的集合，且具有下面的形式： ，其中，其中 ，(V T )* n文法分类：文法分类： A,B V，a T。对文法中的产生式。对文法中的产生式 ： nO型文法型文法: 短语文法。短语文法。 中中至少含一个非终极符。至少含一个非终极符。 n1型文法型文法: 上下文有关文法。它是上下文有关文法。它是0型文法的特例，型文法的特例， 要求要求| | | |(S 例外，例外，S不得出现于产生式右部不得出现于产生式右部)。 n2型文法型文法: 上下文无关文法。它是上下文无关文法。它是1

4、型文法的特例，型文法的特例， 要求产生式左部是一个非终极符要求产生式左部是一个非终极符: A 。 n3型文法型文法: 正则文法。它是正则文法。它是2型文法的特例，要求产型文法的特例，要求产 生式具有下面形式之一生式具有下面形式之一: Aa ，AaB。 文法的乔姆斯基体系文法的乔姆斯基体系 正则文法正则文法 上下文无关文法上下文无关文法 上下文有关文法上下文有关文法 短语文法短语文法 n例：某语言有文法例：某语言有文法G：字母数学：字母数学 标识符，尖括号指非终极符。终标识符，尖括号指非终极符。终 极符极符T：0, 1, 2, , 9, a, b, , z, A, B, , Z, _。P中的产生

5、式有：中的产生式有： 数字数字 0 数字数字 1 数字数字 9 字母字母 a 字母字母 b 字母字母 Z n标识符可以形式化地表示为：标识符可以形式化地表示为： 标识符标识符 字母字母 标识符标识符 标识符字母标识符字母 标识符标识符 标识符数字标识符数字 n例：例：G=(A, B, C, S, a, b, P, S),其中：其中：P 中的产生式集合为：中的产生式集合为： nS AB , S BC nB CC , B b nC AB , C a nA BA , A a n试证明给定串试证明给定串baabaT*，且，且S * baaba ，即即是否是否可以由文法规则推导出该串可以由文法规则推导出

6、该串。 BCS 证明：因为证明：因为baaba串中的每一个字符均串中的每一个字符均 属于属于T，故，故baabaT* S BC bC bAB baB baCC baCa baABa baaBa baaba. BCS 正则文法正则文法 n定义：一个正则文法定义：一个正则文法G定义为四元组定义为四元组(V, T, S, P,), 其中：其中： nV：终极符集合：终极符集合 nT：非终极符集合：非终极符集合 nS: 文法开始符文法开始符 nP：产生式集合，其中的产生式形如：产生式集合，其中的产生式形如： Aa 或或 AaB, aT, A,BV n正则语言：正则语言： 正则文法正则文法G生成的语言：生

7、成的语言： L(G) = |T*且且S* n正则语言的识别：正则语言的识别： 给定正则文法给定正则文法G=(V,T,S,P)，任给串，任给串T* ，是否能被文法是否能被文法G识别。识别。 n正则语言的识别算法正则语言的识别算法 即证明是否有即证明是否有S* . n证明：证明： 设：设：=a1a2aian, aiT 1.若若n=1，判断，判断Sa1是否在是否在P中。中。 2.若若n2，则只需要判断是否有，则只需要判断是否有Sa1B1 有，则往证 有，则往证B1 a2an是否成立。是否成立。 重复上述过程。重复上述过程。 n算法描述：从右向左推导算法描述：从右向左推导 在在P中选择右边为串中选择右

8、边为串的最右字符的最右字符an，符合条件的产生式，符合条件的产生式 左边的非终极符组成一个集合左边的非终极符组成一个集合V1，即：，即： V1=A1|A1anP， 同理：有同理：有 V2=A2|A2an-1A1P，且，且A1V1 Vk=Ak|Ak an-k+1Ak-1P，且，且Ak-1Vk-1 Vn=An|An a1An-1P，且，且An-1Vn-1 检查检查S是否属于是否属于Vn，若有，则说明可以由，若有，则说明可以由S可推导出可推导出串串 ，否则不能推导出，否则不能推导出。 n算法实现：算法实现： for (i=1; i=n; i+) 检查检查aiT否否; V = A|AanP; i=2;

9、 while (i n状态图状态图 状态用结点表示状态用结点表示, 用标有用标有a的从的从q指向指向q的箭头表示的箭头表示 (q,a)=q, 终止状态用双圆圈表示终止状态用双圆圈表示, 起始状态用起始状态用表表 示示 q0 b b q1 a n若输入为若输入为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 例例NFA q0q1q2q3 0,1 0,1 10, 1 n定义：定义： 对两台自动机对两台自动机M1，M2，如果，如果L(M1) = L(M2)，则称，则称M1和和M2等价。等价。 n 定理定理2： 每一台非确定有限自动机都等价于某一每一台非确定有限自动机都等价于某一 台确定有限自动机。台确定有限自动机。 定理定