自然语言理解讲义第二章.ppt

自然语言理解讲义,第二章 句法与句法分析(1): 形式语言与自动机,内容提要,如何描述语言 形式文法定义 乔姆斯基的文法层级 索引文法 范畴文法 自动机 文法判定的复杂度 用形式文法描述自然语言 文法、语言与自动机的关系,如何描述一种语言,枚举 给出语言中的所有句子 对于含无限多个句子的语言不合适 文法(语法) 给出生成语言中所有句子的方法 当且仅当能够用该方法产生的句子才属于该语言 自动机 给出识别该语言中句子的机械方法,形式文法(1),形式文法：四元组G = 终结符（Terminals）的有限集合VT 终结符是句子中实际出现的符号 相当于单词表（有时也称为字母表） 非终结符（Non-terminals）的有限集合VN 非终结符在句子中不实际出现 但在推导中起变量作用 相当于语言中的语法范畴,形式文法(2),起始符S S属于VN 相当于句法范畴中的句子 重写式规则(Rewriting Rules)的有限集合P或 产生式规则(Production Rules)的有限集合P 基本形式： 含义：将改写成 和是终结符和非终结符组成的串 非空，可以为空(),形式文法(3),定义 V*=(VNVT)*，V*。V*是VN和VT上的任意字符串，包括空串()。 V+ =V*-。 直接推导： x y 如果xy是P中的一条规则 推导： * 如果可以经过多次直接推导得到 语言：L(G)= | VT*；S * ,一个例子,例：设形式文法G的VT=the, John, ate, apple，VN=S, NP, VP, ART, N, V, NAME, P=1. SNP VP, 2. VPV NP, 3. NPNAME, 4. NPART N, 5. NAMEJohn, 6. Vate, 7. ARTthe, 8. Ncat，其中NP代表名词短语、VP代表动词短语等等。则句子“John ate the apple”的生成过程如下 SNP VP (重写S) NAME VP (重写NP) John VP (重写NAME) John V NP (重写VP) John ate NP (重写V) John ate ART N (重写NP) John ate the N (重写ART) John ate the apple (重写N),乔姆斯基的文法层级,0型文法,1型文法,2型文法,3型文法,乔姆斯基0型文法,短语结构文法，无限制重写文法 PSG：Phrasal Structure Grammar 对规则形式的约束 对于规则形式没有任何限制,乔姆斯基1型文法,上下文有关语法，上下文敏感语法 CSG：Context Sensitive Grammar 对规则形式的约束： ，是任意串，且的长度小于的长度 A A是非终结符， 、是任意串 以上两种形式等价 敏感：在一定的上下文环境下A可改写为,乔姆斯基2型文法,上下文无关文法，上下文自由文法 CFG：Context Free Grammar 对规则形式的约束： A ：A是非终结符，是任意串 在任何上下文环境下A可改写为,上下文无关文法的一个例子,SaAS Sa ASbA Aba SaASaAaaSbAaaabAaaabbaa,乔姆斯基3型文法,正规文法，正则文法 RG：Regular Grammar 对规则形式的约束 ABx或者Ax，A,B是非终结符，x是终结符 一部正则文法可以表示为一个正则表达式 例子：ab|c*+d|ef|g|h+,乔姆斯基层级以外的文法类别,介于CFG和CSG之间的语法类别 索引文法（IG: Index Grammar） 可以生成anbncn形式的语言 树粘接文法 TAG：Tree Adjoining Grammar 与乔姆斯基语法层级相交叉的语法类别,索引文法(1),索引文法是一个五元组（VN, VT,VI,P,S) VN,VT,S与前面的定义相同 VI是索引的有限集合 P是重写规则的有限集合，规则形式为： 1) A 2) AB(f) 3) A(f) A , B VN, f VI, (VNVT)*,索引文法(2),直接推导()的定义 如果AX1X2Xk是规则集中具有1)形式的规则，那么： A()X1(1) X2(2)Xk(k) 其中，XiVN时，i；XiVT时，i 如果AB(f)是规则集中具有2)形式的规则，那么A()B(f) 如果A(f)X1X2Xk是规则集中具有3)形式的规则，那么： A(f)X1(1) X2(2)Xk(k) 其中，XiVN时，i；XiVT时，i 推导(*)的定义和语言的定义与前面类似,索引文法(3), 例子（规则集） S S() S ABC A() aA B() bB C() cC A a B b C c, 推导 SS() S() S() A()B()C() aA()B()C() aaA()B()C() aaaaB()C() aaaabbbbcccc,可以生成anbncn形式的语言，不是CFG,其他文法,链文法（Link Grammar） 依存文法（Dependency Grammar） 范畴文法（CategorialGrammar）,范畴文法(1),Montague,1970。邹崇理,1995。蒋严&潘海华,1998。白硕,1998 范畴文法的核心思想是把语言中的各种成分对应为某种“类型”/“范畴”，把语言结构的构造过程对应为“类型”/“范畴”之间的演算过程。 http:/www.cs.man.ac.uk/ai/CG/,范畴文法(2)：基本概念,范畴文法里面有两种基本范畴：S和N。粗略地理解，S相当于句子，N相当于名词。 一个语言成分的范畴（类型）由基本范畴S,N加上范畴表达式构造符“”，“/”，括号“（”，和“）”构成。 范畴构造符“”表示“左缺”；“/”表示“右缺”，直观上，可以把它们设想为除号，相应地，范畴的构造就可以看成是带有方向的除法运算。括号表示结合顺序。 当两个语言成分之间发生结合关系时，它们相应的范畴则发生对应的“乘法”运算。运算中最关键的操作就是“约分”。,范畴文法(3)：英语词类的范畴表示,词类 范畴标注 说明 句子 S 基本范畴 名词 N 基本范畴 不及物动词 NS 左方缺少主语 及物动词 (NS)/N或者N(S/N) 左方少主语，右方少宾语 形容词(做定语) N/N 右方少中心语 形容词(做表语) (S/N)S 左方少“缺宾语句子” 副词(做前置状语) (NS)/(NS) 右方少中心语 副词(做后置状语) (NS)(NS) 左方少中心语 介词(做后置状语) (NS)(NS)/N 右方少介词宾语 介词(做后置定语) (NN)/N 右方少介词宾语 冠词 N/N 右方少名词 代词(主格) S/(NS) 右方少不及物动词 代词(宾格) (S/N)S 左方少“缺宾语句子”,范畴文法(4)：范畴演算,句子的构造过程就是语言成分所对应的范畴的演算过程。 一个单词串的演算的结果或者是S，或者不是S，前者即为合法的句子，后者则是不合法的句子。 演算的具体操作分为两种：一种叫做“应用”(Application)，简记为A；一种叫做“合成”(Composition)，简记为C。 应用就是完整的约分，即分母被约掉，只剩下分子作为结果；比如： S/N N S N NS S 合成就是约分后范畴表达式仍然带着分母。比如： S/(NS) (NS)/N S/N,范畴文法(5)：范畴词典,he S/(NS) is (NS)/N a N/N clever N/N boy N,范畴文法(6)：范畴词典,He is a clever boy.,S/(NS) (NS)/N N/N N/N N,-C,S/N,-C S/N -C S/N -A S,范畴演算的语言学假设,假设了所有结构都是由词汇负载的，这样才能从词汇的范畴标记推导出各个上级结构成分的范畴标记； 假设了所有结合必定是邻接成分的结合，而不可能有跨越邻接成分的超距结合，这样才能依托邻接关系实现范畴标记的约分计算； 假设了严格的语序关系，这样才能从确定方向上找到约分的对象； 假设了每个结构必须填项完备，这样才能在最后获得一个分母约干净了的S标记。,范畴文法存在的问题,1 范畴标记和词类不是一一对应的，要在具体的语流中确定具体词的范畴标记有相当的难度，甚至无异于先要理解。 2 不负载在词上面的结构（如汉语中的联合结构、连谓结构等）就很难纳入范畴语法的框架中去表达。 3 超距相关的成分（如“王冕死了父亲”中的“王冕”和“父亲”）在范畴文法的框架中无法建立约分关系。 4 象汉语这样语序灵活、填项经常不完备（省略）的语言，用范畴文法去描述会遇到许多麻烦问题。,图灵机(1)：直观描述,B B B B a1 a2 ai an B B B B B B,有限状态控制器,双向可读写纸带,在每一个时刻，可以定义图灵机的格局为(q,a,i) 其中q为当前状态，a为当前纸带上的字符串，i为当前读写头的位置。B为空白字符。,图灵机(2)：形式定义,图灵机是一个六元组 M= ( Q, , , , q0, F) Q为自动机状态的有限集合 一个有限的字符集合，其中空白字符B , 为输入字符集合，B 是一个状态转移函数：QQR,L,S R,L,S分布表示读写头左移、右移或者不动 q0Q为初始状态 FQ为终止状态集,图灵机(3)：能接受的字符串,开始时，纸带中间有n个字符构成输入串，余下的无穷多个字符为空白字符，空白字符不是输入符号 开始时，读写头处于输入串的最左端，图灵机的状态为q0 如果图灵机M对于字符串在执行过程中进入某个接受状态，称为M接受字符串；如果执行过程中遇到一个格局在状态转移函数中没有定义，那么称M不接受字符串,线性有界自动机,线性有界自动机的构造与图灵机完全一致 对图灵机的限制：纸带存在一个左右边界（用两个特殊符号来标识），图灵机的执行过程中读写头位置不能超出边界 线性有界自动机所识别的语言等价于1型语法所生成的语言,下推自动机,下推自动机是一个七元组 M=( Q, , , , q0, Z0, F ) Q为自动机状态的有限集合 为输入纸带上字符的有限集合 为堆栈字符的有限集合 q0Q为初始状态 Z0是堆栈中的一个特殊符号，表示栈底 FQ为终止状态集 是一个状态转移函数：Q()Q*,有限状态自动机,有限状态自动机是一个七元组 M=( Q, I, U, , , q0, F ) Q为自动机状态的有限集合 I为输入字符的有限集合 O为输出字符的有限集合 是一个状态转移函数：QIQ 是一个输出函数：QIU q0Q为初始状态 FQ为终止状态集,两种有限状态自动机,有限状态接收机（Acceptor）是一个五元组M=( Q, I, , q0, F ) 。是没有输出的有限状态自动机。 有限状态转录机（Transducer）是一个六元组M=( Q, I, U, , , q0) 。有输出，但没有终止状态的有限状态自动机。,有限状态自动机的应用,有限状态自动机具有简单、直观、高效的特点，在很多领域中得到了广泛的应用 词典构造（Xerox Europe） 机器翻译（Alshiwiswork） 有限状态机自动机通过递归（输入另一个自动机的识别结果）可以实现上下文无关语法的描述能力 有限状态转录机可以进行翻译,文法的判定复杂度,PSG：半可判定对于一个属于0型语言的句子L，总可以在确定步内判断出“是”；但对于一个不属于0型语言的句子L，不存在一个算法，可以在确定步内判断出“否”。 CSG：可判定，复杂度：NP完全 CFG：可判定，复杂度：多项式 RG：可判定，复杂度：线性,文法、自动机和语言,用什么文法描述自然语言,正则语法描述能力太弱、上下文有关语法计算复杂度太高，上下文无关语法使用最为普遍 从描述能力上说，上下文无关语法不足以描述自然语言自然语言中上下文相关的情况非常常见 从计算复杂度来说，上下文无关语法的复杂度是多项式的，其复杂度可以忍受 为弥补上下文无关语法描述能力的不足，需要加上一些其他手段扩充其描述能力,上下文无关文法与句子结构,上下文无关文法的二分特性与人类心理思维规律比较接近。 上下文无关文法能反映自然语言句子的层次特性，从而得到句子的句法结构。,上下文无关文法与句子结构,上下文无关文法能表示句法歧义。 例4：“They are flying planes.”可有两种句法结构,