自然语言，形式语法与自动机 北京大学 哲学系 郑 植 2016.2.23

语言与语法 从数学的观点看，自然语言的表达式是一个个有穷长的符号串（其中的符号可以是字、词、音节等）。 但并非每个串都是自然语言允许的合法的表达式。 语法（grammar）的作用就是以某种方式在所有有穷串的集合中“选”出一个子集，使得该子集中的串是“合法”的。 设 A 是符号集，则 A* 表示 A 的全体有穷符号串的集合（包括空串 e）。 “联结”函数 ︵：A*→A*，a︵b＝ab。 结构 <A*, ︵, e> 是幺半群：(a︵b)︵c＝a︵(b︵c)，a︵e＝e︵a＝a。

1.形式语法 一个形式语法（formal grammar，简称“语法”），实质上可以看作是一个基于公理和推演规则的推演系统。

派生与生成

几个形式语法的例子

树 语法生成串的过程以及串的语法结构可以通过（有序）树形图清晰地表现出来。树可以表现出：句子成分的层及分组信息、语法类型信息和顺序信息。

例6 一个Parser程序

几个关于树的语法分析中经常用到的概念 Dominance, immediately dominance Belong to, command, constituent-command Tom told Andy that yesterday Jack hurt himself. himself 指谁？ Precedence

乔姆斯基层级 形式语法的分类：按照重写规则的限制由弱增强，或者说语法生成能力的由强减弱，分为Type 0至Type 3。

乔姆斯基层级 IL是Type 3。

2.自动机 自动机是一种理想化的数学计算装置。在自然语言语法处理中，可以想象自动机可以用来检验符号串的合法性——将一个符号串输入给自动机，由自动机依据形式语法判定其是否合法。如果合法，自动机给出结果“接受”，反之给出结果“拒绝”。 据判定规则和工作原理的不同，自动机根可分为多种。不同种类的自动机与不同类型的形式语法存在对应关系。

2.1有限状态自动机

正则语言（Type 3）就是有限状态自动机语言。 正则语言由正则语法生成，用有限状态自动机识别。 A→xB：读取x，由状态A进入状态B A→x：读取x，由状态A进入终止状态F 给定一个有限自动机，构造一个 Type 3 语法： 若 qj 不是终止状态，<qi, x, qj>：qi→xqj 若 qj 是终止状态，<qi, x, qj>：qi→x 非终结符集即状态集，终结符集即字母表 正则语法的缺陷：只能向右扩展。 英语不是正则语言。

x1 ... xn y1 ... yn died（xi∈A，yi∈B）。 英语不是正则语言。 (1)The cat died. (2)The cat the dog chased died. (3)The cat the dog the rat bit chased died. (4)The cat the dog the rat the elephant admired bit chased died. (the + CN)n + (TV)n-1 + IV 设 A 是“the + CN”的集合，B 是 TV 的集合，则上述句型的字符串具有形式： x1 ... xn y1 ... yn died（xi∈A，yi∈B）。 设 L＝{x1 ... xn y1 ... yn died | 任给 xi∈A，yi∈B，n≥1}。 L 由英语和正则语言A*︵B*︵{died}相交得到。 正则语言对交运算封闭。若英语是正则语言，则 L 也是。 但 L 不是（证明类似于{anbn| n≥0}）。 因此英语不是正则语言。（Chomsky, 1956; 1957, Chapter 3）

英语不是正则语言。 英语中存在许多跨主谓结构的一致与对应。 Anyone1 who feels that if2 so-many3 more4 students5 whom we6 haven't6 actually admitted are5 sitting in on the course than4 ones we have that3 the room had to be changed, then2 probably auditors will have to be excluded, is1 likely to agree that the curriculum needs revision. （Chomsky & Miller, 1963） 1 2 3 4 5 6 6 5 4 3 2 1 {xxR| x∈{a, b}*}不是正则语言（因为它与正则语言 aa*bbaa* 的交{anb2an| n≥2}不是正则语言）。

2.2下推自动机

上下文无关语言由上下文无关语法生成，可使用下推自动机进行识别。 给定一个上下文无关语法，构造一个下推自动机： 状态集{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 & Papadimitriou（1981）

一个瑞士德语中的例子（Schieber, 1985）： 自然语言是上下文无关的吗？ 一个瑞士德语中的例子（Schieber, 1985）： Jan säit das mer d'chind em Hans es huus lönd hälfe aastriiche. John said that we the chils-Acc Hans-Dat the house-Acc let help paint 约翰 说 我们 小孩 汉斯 房屋 让 帮助 粉刷 约翰说，我们让小孩帮助汉斯粉刷房屋。 交叉对应：小孩—让，汉斯—帮助，房屋—粉刷。 将瑞士德语与如下一个正则语言相交： Jan säit das mer (d'chind)* (em Hans)* es huus haend wele (laa)* (hälfe)* aastriiche 约翰说我们(孩子)*(汉斯)*房屋想要(让)*(帮助)*粉刷 得到的结果 Jan säit das mer (d'chind)n (em Hans)m es huus haend wele (laa)n (hälfe)m aastriiche wanbmxcndmy 不是上下文无关语言。 上下文无关语言同正则语言的交是上下文无关语言，因此瑞士德语不是上下文无关语言。 瑞士德语的亲属语言荷兰语因为没有格标记，故无法得出类似结论。

2.3图灵机

图灵机除了可以看作语言接受装置外，还可以看作是一个函数计算装置。 输入字符串→计算（改写字符串）→输出字符串 如果不停机，则认为该“函数”对输入的字符串无定义。 例19（1）f:{a,b}*→{a,b}*，f(u)＝v，v 是 u 中 a, b 对调的结果。 可以实现自然数的计算。如 ...#an#am#... → ...#an+m#...。 图灵机可计算的函数称递归部分函数。对所有输入均能停机的，称递归函数。 图灵机还可看做是一个生成装置。 值域内的元素可视为由图灵机“生成”，该值域称递归可枚举集。 以下三个命题彼此等价： A 被某个图灵机接受。 A 是某个递归部分函数的值域。 A 是递归可枚举集。

Type 0 语法生成的语言恰好就是能被图灵机接受的语言。也就是说，Type 0 语法生成的语言是递归可枚举集。 给图灵机两条带子 Tape 1：#输入的字符串# Tape 2：#S# 图灵机根据 G 的规则重写 S 。图灵机比较重写后的 Tape 2 是否与 Tape 1 一致。如一致，则停机；如不一致，则继续用 G 的规则重写 Tape 2，然后再比较。如果没有可使用的规则，则用一种预先定义好的方式进入死循环而不停机。 给定一个图灵机，找出它对应的语法（语言）。 操作 <q,a>→<q',b> 可对应于规则 qa→q'b。 以下四个命题彼此等价： A 被某个图灵机接受。 A 是某个递归部分函数的值域。 A 是递归可枚举集。 A 由某个Type 0 语法生成。

2.4线性有界自动机 线性有界自动机与图灵机基本相同，只是输入带子有左右界限，读写头不得更改界限，其运动也不得超出这一界限。 线性有界自动机用于识别上下文有关语言。

2.5自动机类型与形式语法和语言类型的对应关系 Chomsky 与 Kuroda：四种语法及其语言分别能与四种自动机一一对应：某语言能用某种类型的自动机识别，当且仅当，它能用该种类型语法生成。 Type 0 —— 图灵机 Type 1 —— 线性有界自动机 Type 2 —— 下推自动机 Type 3 —— 有限状态自动机 这一结果对计算机的编译技术很有帮助，极大地推动了计算机的自然语言处理工作。

形式语法理论是形式主义语言学研究的核心理论。 语言本体研究（如《英语语音模式》） 计算语言学 心理学 语言哲学：天赋语言观，反对语言工具论 问题 语法独立性

3.应用举例：现代汉语歧义结构分析 计算机分析自然语言的语法结构时，需要根据给定的语法规则构建短语或句子的语法生成树。有歧义的短语或句子可以合语法地构建结构不同的树。如果这些不同的树在人类看来并非都可取，那么计算机就需要通过某种手段排除那些合语法但不可取的树，即进行计算机的排歧。 从人的角度来看，自然语言歧义大致可分为结构层次歧义、结构关系歧义、语义关系歧义和语用歧义。而计算机首先面临的问题是结构层次歧义和结构关系歧义的处理，语义和语用方面的歧义处理更深入也更困难。 结构层次歧义：老王做了两个儿子爱吃的菜。 结构关系歧义：出租汽车，牛奶面包 语义关系歧义：谁都不认识，张三借了李四三百元 语用歧义：——想来点咖啡吗？——咖啡可是很提神的。

总的来说，消歧主要依据语言结构中各级语言单位的功能特征，如在词典中记录每个词语占据句法结构位置的能力，通过规则的合一约束描述短语的功能特征，以及规定功能特征的取值如何发生动态变化等。

参考文献 Partee, B., Meulem A., & Wall, R. Mathematical methods in linguistics. Springer-Verlag, 2009. Chapt 16-20. Chomsky, N. Syntactic structures, The Hague, Mouton & Co. 1957. Chomsky, N. Formal properties of grammar, in Luce Bush & Galanter (eds.), pp. 323-418. 1963. Cann, R. Formal semantics. Cambridge Uniersity Press, 1993. Shieber, S.M. Evidence against the context-freeness of natural language, Linguistics and Philosophy 8, 333-343. Reprinted in Savitch, Bach, Marsh, and Naveh (eds.), 1985.