自然语言理解(03)形式语言与自动机

自然语言理解第三章形式语言与自动机及其在自然语言处理中的应用3.1基本概念3.2形式语言3.3自动机理论3.4自动机在自然语言处理中的应用3.1基本概念•3.1.1图•3.1.2树•3.1.3字符串3.1.1图•图的本质是二元关系•无向图和有向图•连通图•回路例子3.1.2树(tree)：一个连通的无回路的无向图称为树（或称自由树）。如果树中有一个结点被特别地标记，则这棵树被称之为根树，这个被特别标记的结点被称之为根结点。例子3.1.3字符串(string)字符串定义：假定Σ是字符的有限集合，它的每一个元素称之为字符。由Σ中字符相连而成的有限序列被称之为Σ上的字符串（或称符号串）。特殊地，不包括任何字符的字符串称为空串，记作ε。符号串的长度：符号串中符号的个数。符号串x的长度用|x|表示。|ε|=0。包括空串的Σ上字符串的全体记为Σ*。q字符串操作假定Σ是字符的有限集合，x,y是Σ上的符号串字符串连接：则把ｙ的各个符号写在ｘ的符号之后得到的符号串称为ｘ与ｙ的连接，记作ｘｙ。例如：Σ={a,b,c},x=ab,y=cba那么，xy=abcba(2)符号串集合的乘积设A,B是符号串的集合，则A,B的乘积定义为：3.1几个基本概念例如:设A={aa,bb},B={cc,dd,ee}，则AB={aacc,aadd,aaee,bbcc,bbdd,bbee}A2={aaaa,aabb,bbaa,bbbb}(3)闭包3.1几个基本概念3.2形式语言3.2.1概述3.2.2形式语法的定义3.2.3形式语法的类型3.2.4CFG识别句子的派生树表示q关于语言的定义按照一定规律构成的句子和符号串的有限或无限的集合。－Chomsky语言可以被看成一个抽象的数学系统。（吴蔚天，1994）语言描述的三种途径v穷举法——只适合句子数目有效的语言。v语法描述——生成语言中合格的句子。v自动机——对输入的句子进行检验，区别哪些是语言中的句子，哪些不是语言中的句子。3.2形式语言q形式语言的直观意义形式语言是用来精确描述语言（包括人工语言和自然语言）及其结构的手段。形式语言学也称代数语言学。3.2形式语言q形式语法的定义3.2形式语言q推导的定义3.2形式语言q最左推导、最右推导和规范推导约定每步推导中只改写最左边的那个非终结符，这种推导称为“最左推导”。约定每步推导中只改写最右边的那个非终结符，这种推导称为“最右推导”。最右推导也称规范推导。3.2形式语言3.2形式语言3.2形式语言q正则文法3.2形式语言q上下文无关文法（CFG,context-freegrammar）3.2形式语言q上下文有关文法（CSG,context-sensitivegrammar）3.2形式语言q无约束文法（无限制重写系统）3.2形式语言q语言与文法类型的约定如果一种语言能由几种文法所产生，则把这种语言称为在这几种文法中受限制最多的那种文法所产生的语言。例3.5：G=({S,A,B},{a,b},P,S)G为上下文无关文法。L(G)={等数量的a和b构成的链}3.2形式语言qCFG产生的语言句子的派生树表示3.2形式语言例如，G=({S,A},{a,b},P,S)P:S→bAA→bAAA→aG所产生的一个句子bbaa可以由下面的生树表示：aSbAbAAaS→bAA→bAAA→a3.2形式语言q上下文无关文法的二义性一个文法G，如果存在某个句子有不只一棵分析树与之对应，那么称这个文法是二义的。如文法：G(E):E→E+E|E*E|i对于句子i+i*i有两棵对应的分析树。E*EiiEE+EiE+EiiEE*Ei3.2形式语言q语言与识别器的对应关系识别器是有穷地表示无穷语言的另一种方法。每一个语言的句子都能被一定的识别器所接受。识别器类型图灵机线性带限自动机下推自动机有限自动机语言类型0型1型2型3型3.2形式语言3.3自动机理论•3.3.1有限自动机•3.3.2正则文法与自动机的关系•3.3.3上下文无关文法与下推自动机•3.3.4图灵机•3.3.5线性界限自动机3.3自动机理论q确定的有限自动机(DefiniteAutomata,DFA)qDFA示意图有限控制器aababba输入头输入带3.3自动机理论q状态变换图qq’a为了明确起见，终止状态用双圈表示，起始状态用有“开始”标记的箭头表示。3.3自动机理论q0q1qDFA定义的语言例3.6：0q3开始00q2110T(M)={含偶数个0和偶数个1的链}3.3自动机理论q不确定的有限自动机(Non-definiteAutomata,NFA)3.3自动机理论qNFA与DFA的区别q0q3q4001q11q20,10,1例3.7：0,1开始该自动机为不确定自动机；句子x=01011可以被接受。3.3自动机理论qNFA与DFA的关系定理3.1：设L是一个被NFA所接受的句子的集合，则存在一个DFA，它能够接受L。（证明见另一ppt）说明：由于DFA与NFA所接受的是同样的链集，所以一般情况下无需区分它们，二者统称为有限自动机(FiniteAutomata)。3.3自动机理论q正则文法与有限自动机的关系3.3自动机理论q由G构造M的一般步骤：3.3自动机理论3.3自动机理论等价的NFA的状态变换图为：SBT开始aaba3.3自动机理论结论：对于任意一正则文法，总可以构造一个识别器——DFA。3.3自动机理论…q下推自动机(Push-DownAutomata,PDA)的理解PDA可以看成是一个带有附加的下推存储器的有限自动机，下推存储器是一个栈。如下图所示：cddbbb…Z0Z有限控制器只读头读写头下推存储器输入带3.3自动机理论qPDA的定义3.3自动机理论3.3自动机理论q符号约定*3.3自动机理论q下推自动机接受的语言（终止状态接受标准）下推自动机M所接受的语言定义为：例3.9下推自动机M=(,Q,,,q0,Z0,F)接受语言3.3自动机理论对于输入abbcbba下推自动机M的处理步骤为：状态输入栈运用的规则0abbcbba#-0bbcbbaA#10bcbbaBA#20cbbaBBA#21bbaBBA#31baBA#511aA##543.3自动机理论3.3自动机理论下推自动机接受的语言（空存储器接受标准）•即对于给定的输入句子x，当输入头指向x的末端，如果下推存储器变为空，则认为x被PDAM所接受，而不管这时PDA的状态q是否在终止状态集F中。q图灵机的理解有限控制器a1a2ai…an…BB…输入/输出带读/写头3.3自动机理论q图灵机与有限自动机的区别图灵机可以通过其读／写头改变输入带的字符。q图灵机的定义一个图灵机T可以表达成一个六元组：3.3自动机理论q图灵机的解释(q,A1A2…An,i)(p,A1A2…Ai-1XAi+1…An,i+1)即T的读/写头在i位置写入符号X，并将读/写头向右移动一个位置。T3.3自动机理论T3.3自动机理论给定一个识别语言L的图灵机T，不失一般性，我们假定每当输入被接受时，T就停机，即没有下一个动作。另一方面，对于未接受的链，T可能不停机。q图灵机接受的语言如果T的两个格局X和Y之间的基本移动（包括不移3.3自动机理论q定理定理３．３如果L是一个由0型文法产生的语言，则L可被一个图灵机所接受。定理３．４如果L可被一个图灵机所接受，则L是一个由0型文法产生的语言。3.3自动机理论q线性带限自动机线性带限自动机是一个确定的单带图灵机。其读写头不能超越原输入带上字符串的初始和终止位置。即线性带限自动机的存储空间被输入符号串的长度所限制。定义：一个线性带限自动机M可以表达成一个6元组：3.3自动机理论q线性带限自动机所接受的语言3.3自动机理论q定理定理３．５：如果L是一个前后文有关语言，则L由一个不确定的线性带限自动机所接受。反之，如果L被一个线性带限自动机所接受，则L是一个前后文有关语言。3.3自动机理论各类自动机的区别与联系主要区别：各类自动机的主要区别是它们能够使用的信息存储空间的差异：有限状态自动机只能用状态来存储信息；下推自动机除了可以用状态以外，还可以用下推存储器（栈）；线性带限自动机可以利用状态和输入/输出带本身。因为输入/输出带没有“先进后出”的限制，因此其功能大于栈；而图灵机的存储空间没有任何限制。识别语言的能力：有限自动机等价于正则文法；下推自动机等价于上下文无关文法；线性带限自动机等价于上下文有关文法，图灵机等基于0型文法。3.4自动机在自然语言处理中的应用•3.4.1单词拼写检查•3.4.2单词形态分析•3.4.3词性消歧3.4自动机在自然语言处理中的应用q有限自动机用于英语单词拼写检查[Oflazer,1996]设X为拼写错误的字符串，其长度为m，Y为X对应的正确的单词（答案），其长度为n。则X和Y的编辑距离ed(X[m],Y[n])为：从字符串X转换到Y需要的插入、删除、替换和交换两个相邻的基本单位（字符）的最小个数。如：ed(recoginze,recognize)=1ed(sailn,failing)=3一个确定的有限状态机R定义为：3.4自动机在自然语言处理中的应用3.4自动机在自然语言处理中的应用•一个基于有限状态机的识别器可以看作一个弧上有字母标记a的有向图，字母表上的字母构成的所有合法单词都是有限状态机中的一条路径。那么，字符串识别的过程就是对有向图从初始状态到终止状态遍历的过程，一条路径从初始状态到终止状态经过的所有弧上的字母连起来构成一个字符串。如果给定一个输入串，对其进行拼写状态检查的过程实际上就是在给定阙值t(t0)的范围内，寻找所有与输入串的编辑距离小于t的路径，这些路径从初始状态到终止状态经过的所有弧上的字母连接起来就是要找的与输入串最相似的单词。……………………q0abmz对于某一字符串X，搜索与之编辑距离最短的单词(路径)。说明：蓝色节点表示终结节点，下同。3.4自动机在自然语言处理中的应用•为了提高搜索速度，可以把搜索空间限定在一个较小的范围内，尽早把那些编辑距离超过给定阙值t的路径剪枝。为了判断哪些路径应该被剪枝，Oflazer提出了剪除编辑距离的概念，用于度量错误的输入串的字串与候选正确串之间的最小编辑距离。设Y是一局部候选串（拼写正确），长度为n，X是出错的输入串，长度为m。3.4自动机在自然语言处理中的应用cuted(X[m],Y[n])=min{ed(X[i],Y[n])}liu其中，l=max(1,n-t),u=min(m,n+t)。例如：t=2,X=reprter(m=7),Y=repo(n=4)，那么：l=max{1,4-2}=2;u=min{7,4+2}=6cuted(reprter,repo)=min{ed(re,repo)=2,ed(rep,repo)=1,ed(repr,repo)=1,ed(reprt,repo)=2,ed(reprte,repo)=3}=13.4自动机在自然语言处理中的应用3.4自动机在自然语言处理中的应用•因此，除了边界情况，被考虑的含拼写错误的字符串X的长度应介于n-t和n+t之间。要保持长度上符合条件，长度小于n-t和大于n+t的都不符合条件。•有限自动机形成候选串Y的过程就是构成一个有向图，因此，可以通过稍微修改图的深度优先搜索算法来实现所有Y的生成过程。3.4自动机在自然语言处理中的应用q有限自动机用于英语单词形态分析[Allen,1995]英语单词形态变化非常普遍：例如：eat:eats,eating,ate,eatenhappy:happier,happiestseed?通常使用有限状态变换器(finitestatetransducers,FSTs)FST与DFA的区别：FST有输出，DFA和有限状态机(finitestatemachine,FSM)没有输出。3.4自动机在自然语言处理中的应用1234511happy67i:y:+89e101213rst识别单词：happy,happier,happiest可转换的形式：happierhappy+e