第三章 自然语言的处理案例实例.ppt

这个句子的识别还可以在网络中走其它弧，如由状态c输入“swallow”也可以走弧c→d，但接下来输入“flies”时就被拒绝识别了。由此可看出网络识别的过程应找出各种可能的路径，因此算法要采用并行算法或回溯算法。 * (1)并行算法。并行算法的关键是在任何一个状态都要选择所有可以到达下一个状态的弧,同时进行试验。 (2)回溯算法。回溯算法则是在所有可以通过的弧中选出一条往下走,并保留其他可能性,以便必要时可以回过来选择之。这种方式需要一个堆栈结构。 （2）递归转移网络（RTN） 是对有限转移网络的一种扩展，在RTN中每条弧的标注不仅可以是一个终结符（词或词类），而且可以是一个用来指明另一个网络名字的非终结符。 例如，下面是一部上下文无关语法： S →NP V NP PP* NP →T ADJ* N PP* PP →P NP X*表示符号X可以出现 零次或多次。 （3）扩充转移网络（ATN） ATN语法属于一种增强型的上下文无关语法，即用上下文无关文法描述句子文法结构，并同时提供有效的方式将各种理解语句所需要的知识加到分析系统中，以增强分析功能，从而使得应用ATN的句法分析程序具有分析上下文有关语言的能力。 ATN主要是对转移网络中的弧附加了过程而得到的。当通过一个弧的时候，附加在该弧上的过程就会被执行。这些过程的主要功能是（I）对文法特征进行赋值；(II)检查数（number）或人称（第一、二或三人称）条件是否满足，并据此允许或不允许转移。 ATN在三方面对RTN作了扩展和增强： （1）添置了一组寄存器，用来存储分析过程中得到的中间结果和有关信息。 例如，“小王研究鲁迅的文章”可能先被分析为NP＋VP，但发现后面的词是“发表”，则要回到前面的某个转移点重新分析，选择另一条路。 （2）每条弧上除了用句法范畴来标注以外，可以附加任意测试，只有当弧上的这种测试成功之后才能用这条弧。 （3）每条弧上还可以附加某些动作，当通过一条弧时，相应的动作便被依次执行，这些动作主要用来设置或修改寄存器的内容。 例：一个简单的名词短语(NP)的扩充转移网 络， 网络中弧上的条件和操作如下所示： 该网络主要是用来检查NP中的数的一致值问题。 特征是Number(数),有两个值：singular(单数)和plural(复数),缺省值是?(空)。 C是弧上的条件,A是弧上的操作,*是当前词,proper是专用名词,det是限定词,PP是介词短语,*.Number是当前词的“数”。 该扩充转移网络有一个网络名NP。网络NP可以是其他网络的一个子网络,也可以包含其他网络,如其中的PP就是一个子网络,这就是网络的递归性。 弧NP-1将当前词的Number放入当前NP的Number中； 而弧NP-4则要求当前noun的Number与NP的Number是相同时，或者NP的Number为空时,将noun作为NP的Number，这就要求det的数和noun的数是一致的。因此this book,the book,the books,these books都可顺利通过这一网络,但是this books,或these book就无法通过。 如果当前NP是一个代词(pron.)或者专用名词(proper),那么网络就从NP-5或NP-6通过,这时NP的数就是代词或专用名词的数。PP是一个修饰前面名词的介词短语,一旦到达PP弧就马上转入子网络PP. 例：一个句子的ATN,主要用来识别主、被动态的句子。 S网络中所涉及的功能名和特征维包括： 功能名：Subject(主语),Direct-Obj(直接宾语), Main-Verb(谓语动词), Auxs.(助动词), Modifiers(修饰语)。 特征维： Voice(语态)：Active(主动态),Passive(被动态),缺省值是Active。 Type(动词类型)：Be,Do,Have,Modal,Non-Aux,缺省值是Non-Auxa Form(动词式)：Inf不定式),Present(现在式),Past(过去式),Pres-part(现在分词),Past-part(过去分词),缺省值是Present。 上下文有关文法（CSG） 如果所有产生式都有右边部分长度大于等于左边部分，那么G是上下文有关文法 上下文无关文法（CFG） 如果如果所有产生式的左边部分都是单个非终极符号，那么G是上下文无关文法 正则文法（RG） 如果所有产生式的右边部分都是以终极符号开始、含有至多一个非终极符号、如果有非终极符号则出现在最右边，那么G是正则文法。 请判断以下文法的类型 G1: S→CD Ab→bA C