资源描述：
《自然语言,形式语法与自动机.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、自然语言，形式语法与自动机北京大学哲学系郑植2016.2.231语言与语法从数学的观点看，自然语言的表达式是一个个有穷长的符号串（其中的符号可以是字、词、音节等）。但并非每个串都是自然语言允许的合法的表达式。语法（grammar）的作用就是以某种方式在所有有穷串的集合中“选”出一个子集，使得该子集中的串是“合法”的。设A是符号集，则A*表示A的全体有穷符号串的集合（包括空串e）。“联结”函数︵：A*→A*，a︵b＝ab。结构是幺半群：(a︵b)︵c＝a︵(b︵c)，a︵e＝e︵a＝a。21.形式语法一个
2、形式语法（formalgrammar，简称“语法”），实质上可以看作是一个基于公理和推演规则的推演系统。3派生与生成4几个形式语法的例子567树8语法生成串的过程以及串的语法结构可以通过（有序）树形图清晰地表现出来。树可以表现出：句子成分的层及分组信息、语法类型信息和顺序信息。9例6一个Parser程序几个关于树的语法分析中经常用到的概念10Dominance,immediatelydominanceBelongto,command,constituent-commandTomtoldAndythatyesterday
3、Jackhurthimself.himself指谁？Precedence乔姆斯基层级11形式语法的分类：按照重写规则的限制由弱增强，或者说语法生成能力的由强减弱，分为Type0至Type3。乔姆斯基层级12IL是Type3。2.自动机13自动机是一种理想化的数学计算装置。在自然语言语法处理中，可以想象自动机可以用来检验符号串的合法性——将一个符号串输入给自动机，由自动机依据形式语法判定其是否合法。如果合法，自动机给出结果“接受”，反之给出结果“拒绝”。据判定规则和工作原理的不同，自动机根可分为多种。不同种类的自动机与不
4、同类型的形式语法存在对应关系。2.1有限状态自动机14151617正则语言（Type3）就是有限状态自动机语言。正则语言由正则语法生成，用有限状态自动机识别。给定一个Type3语法，构造一个有限自动机：A→xB：读取x，由状态A进入状态BA→x：读取x，由状态A进入终止状态F给定一个有限自动机，构造一个Type3语法：若qj不是终止状态，：qi→xqj若qj是终止状态，：qi→x非终结符集即状态集，终结符集即字母表正则语法的缺陷：只能向右扩展。英语不是正则语言。18英语不是正则语言。
5、(1)Thecatdied.(2)Thecatthedogchaseddied.(3)Thecatthedogtheratbitchaseddied.(4)Thecatthedogtherattheelephantadmiredbitchaseddied.(the+CN)n+(TV)n-1+IV设A是“the+CN”的集合，B是TV的集合，则上述句型的字符串具有形式：x1...xny1...yndied（xi∈A，yi∈B）。设L＝{x1...xny1...yndied
6、任给xi∈A，yi∈B，n≥1}。L由英语和正则
7、语言A*︵B*︵{died}相交得到。正则语言对交运算封闭。若英语是正则语言，则L也是。但L不是（证明类似于{anbn
8、n≥0}）。因此英语不是正则语言。（Chomsky,1956;1957,Chapter3）19英语不是正则语言。英语中存在许多跨主谓结构的一致与对应。Anyone1whofeelsthatif2so-many3more4students5whomwe6haven't6actuallyadmittedare5sittinginonthecoursethan4oneswehavethat3theroomh
9、adtobechanged,then2probablyauditorswillhavetobeexcluded,is1likelytoagreethatthecurriculumneedsrevision.（Chomsky&Miller,1963）123456654321{xxR
10、x∈{a,b}*}不是正则语言（因为它与正则语言aa*bbaa*的交{anb2an
11、n≥2}不是正则语言）。2.2下推自动机202122上下文无关语言由上下文无关语法生成，可使用下推自动机进行识别。给定一个上下文无关语法，构造一个下推自动机：
12、状态集{q0,q1}，初始状态q0，终止状态q1。输入字母表VT，栈字母表VT∪VN。(q0,e,e)→(q1,S)，对每条A→，有(q1,e,A)→(q1,)，对每个终结符a，有(q1,a,a)→(q1,e)。给定一个下推自动机，构造一个上下文无关语法。Hopcroft&Ullman（1979）Lewis&Papadimit
