NLP：形式语言与自动机

本文为《自然语言处理》课程中“形式语言与自动机”一讲的整理。

这里我们要回答的一个基本问题是：语言能否被有限条规则精确刻画？形式语言理论给出了肯定的回答——用一套重写规则（文法）就能生成一个（可能是无限的）句子集合，而有限自动机则从识别一侧给出对应的机器模型。

本讲先建立文法与推导的形式定义，再给出 Chomsky 四型分类，最后落到有限自动机与正则文法之间的等价关系。

形式语言

语言是句子集合

语言学视角下：“语言是人类所特有的用来表达意思、交流思想的工具，是一种特殊的社会现象，由语音、词汇和语法构成一定的系统。”（《现代汉语词典》）

数学视角下：“语言可以被看成一个抽象的数学系统。”（吴蔚天）

形式语言理论的视角下：“语言是按照一定规律构成的句子和符号串的有限或无限的集合。”（N. Chomsky）

一种语言就是一个句子集合。形式语言理论的目标，就是为这样的集合寻找精确、有限的描述手段。这套理论由 Chomsky 在 20 世纪 50 年代创立，他被视为现代语言学之父。

语言描述的途径

要描述一个语言（即一个句子集合），有三条途径：

穷举法：把语言中的所有句子都枚举出来。这一途径只适用于有限语言。
文法描述：用一组规则生成语言中合格的句子。它能用有限规则刻画无限语言，是形式语言理论的核心。
自动机：对输入的句子进行校验，区别哪些是语言中的句子、哪些不是。

三个动词——枚举、生成、检验——分别概括了三条途径的动作，也勾勒出“文法（生成）”与“自动机（检验）”这一对互补的工具：同一类语言，既可以用文法从内部生成，也可以用自动机从外部识别。

形式语言与产生式

形式语言是用来精确地描述语言（包括人工语言和自然语言）及其结构的手段，因与代数方法密切相关，形式语言学也称代数语言学。其基本表示形式是重写规则（rewriting rule）：

其中、均为由符号构成的串。顾名思义，表示字符串可以被改写成。

从一个初始字符串出发，不断运用重写规则，就能得到新的字符串；而选择不同的规则、以不同的顺序加以运用，就能得到不同的新字符串。重写规则又叫产生式（production）：它“产生”出新的字符串。一个语言，正是由所有能够从初始符号出发、经有限步重写得到的合法字符串构成的。

形式语法

四元组定义

形式语法（形式文法）是一个四元组

其中：

是非终结符的有限集合，也叫变量集或句法种类集；
是终结符的有限集合，规定：
- 终结符与非终结符没有交集，即；
- 终结符与非终结符的并集称为总词汇表；
是一组重写规则的有限集合，其中、是由中元素构成的串，但 至少应含一个非终结符；
，称为句子符或初始符。

举例来说，

就是这样一个文法：为非终结符，为终结符，为初始符。终结符是最终出现在句子里的符号，非终结符则是推导过程中的“中间变量”。

推导

设是一个文法。在上定义关系表示“直接派生”或“推导”。

它的含义是，如果是中的符号串，且是中的产生式，那么。

也就是说，只要当前串中含有某条产生式的左部，就可以把它替换成右部，其余部分、保持不变。在此基础上再引入两个闭包记号：

（按非平凡方式派生）表示的传递闭包，即经过步推导；
$\overset{}{\Rightarrow} $（派生）表示$ \Rightarrow$ 的*自反传递闭包，即经过步推导。

一句话概括： 是一步，是至少一步，是允许零步的任意多步。（这种表示方式与正则表达式里的 + 和 * 的功能有点类似）若上下文已明确是哪个文法，记号下标中的可以省略。

最左推导与最右推导

同一个句子往往存在多种推导顺序。若约定每步只改写最左边的那个非终结符，这种推导称为最左推导；若约定每步只改写最右边的那个非终结符，则称为最右推导。最右推导也称规范推导。

考虑文法

字符串的最左推导为

其最右推导（规范推导）为

两种推导的每一步都合法，最终得到同一个句子。最右推导在编译原理中格外重要，因为它是自底向上语法分析的基础。

句型与句子

最后给出句型的递归定义。一个符号串可被称为文法的句子形式（简称句型），仅当：

是一个句子形式；
如果是一个句子形式，且是中的产生式，则也是一个句子形式。

句型是推导过程中出现的任意符号串，可以含有非终结符。而不含非终结符的句型，称为生成的句子。由文法生成的语言记作，即生成的所有句子的集合：

Chomsky 文法分类

四型文法对照

按产生式形式的限制从严格到宽松，Chomsky 把文法分为四型：

类型	名称	产生式形式	主要特点	典型语言
3 型	正则文法	或	产生式限制最严格，结构简单	正则语言
2 型	上下文无关文法		左部只有一个非终结符，改写不依赖上下文	上下文无关语言
1 型	上下文有关文法		非终结符的改写受上下文影响，通常不缩短串长	上下文有关语言
0 型	无限制文法		对产生式限制最少，表达能力最强	递归可枚举语言

四型之间是严格的包含关系：正则语言上下文无关语言上下文有关语言递归可枚举语言。

限制越严格，能描述的语言就越少，但对应的识别机器也越简单。

正则文法（3 型）

如果文法中的规则都形如

$或$

则称该文法为正则文法（regular grammar, RG）或 3 型文法，且具体称为左线性正则文法（非终结符在终结符左边）。若规则形如，则称为右线性正则文法。

例如以下文法生成“至少一个后接至少三个 ”的串：

其中产生式的右部含两个终结符，不完全符合的形式，可引入新非终结符改写为等价的、。这说明“正则”这一限制针对的是规则能否写成标准形式，必要时总可以通过增加非终结符来规范化。

上下文无关文法（2 型）

如果中的规则都形如

则称该文法为上下文无关文法（context-free grammar, CFG）或 2 型文法。其特点是产生式左部只有一个非终结符，因此无论该非终结符出现在什么上下文中，都可以独立地被改写——这正是“上下文无关”的含义。CFG 是描述自然语言句法、以及程序设计语言语法的核心模型。

例如

生成的语言为，其中、、、，且时，否则。

上下文有关文法（1 型）

如果中的规则都形如

且至少包含一个字符（），则称该文法为上下文有关文法（context-sensitive grammar, CSG）或 1 型文法。这里非终结符之所以能被替换，取决于它左右两侧的、，即上下文。它还有一种等价的长度定义：对每条规则，有、，且 ——替换不会缩短串长。

例如：

产生式中，的改写依赖其左侧的，恰是“上下文有关”的直接体现。

无限制文法（0 型）

如果中的规则都形如（、为字符串），则称为无限制文法（unrestricted grammar, UG）或 0 型文法。它对产生式几乎不加限制，因而表达能力最强，对应递归可枚举语言。

语言类型的约定

一个语言可能同时能被多种类型的文法生成，此时如何判定它的类型？约定是：语言的类型取决于能够生成该语言的文法中，类型最低（限制最严格）的那一种。

例如，等数量的和构成的链可以由 0 型、1 型、2 型文法生成。取其中限制最严格的 2 型，故该语言归为上下文无关语言。其文法为

上下文无关文法与派生树

派生树

CFG 生成句子的过程可以画成一棵树，称为派生树（也称分析树）。它由如下规则构成：

对每个给一个标记作为节点，作为根节点；
若某节点标记为且至少有一个除自身以外的后裔，则（只有非终结符才允许有孩子）；
若某节点标记为，其个直接后裔从左到右依次标记为，则必是中的一条产生式。

例如对

句子的推导为，其派生树为：

树中每个内部节点对应一次产生式的应用，叶节点从左到右的标记串就是所生成的句子。

二义性

一个文法，如果存在某个句子有不只一棵分析树与之对应，就称它是二义性文法。典型例子是带歧义的算术表达式文法

对句子，它有两棵不同的分析树：

一棵把乘法留到更深处、对应先算再算；另一棵把加法放在根、对应先算再乘。二义性是文法本身的属性，同一个语言可以存在无二义性的等价文法。

自然语言中的结构歧义

二义性在自然语言中表现为结构歧义。以下文法

$关于$
$鲁迅文章的$

对短语「关于鲁迅的文章」给出两种推导，因而有两棵派生树：

一棵以展开，结构为「关于〔鲁迅的文章〕」，即「文章」是「关于」的宾语；
另一棵以展开，结构为「〔关于鲁迅〕的文章」，即「关于鲁迅」作定语修饰「文章」。

同一串汉字因句法结构不同而产生两种解释，这正是句法分析需要消解的歧义。它说明自然语言也并不“上下文无关”得那么彻底——语义与上下文常常是消歧的关键。

有限自动机

从识别一侧看，最基本的一类机器是有限自动机（finite automata, FA），它分为确定与非确定两种。

确定有限自动机（DFA）

确定有限自动机是一个五元组

其中是输入符号的有穷集合，是状态的有限集合，是初始状态，是终止状态集合，是到的映射。

它的工作方式是：有限控制器从左到右依次从输入带上读入字符，初始时处于，输入头指向串的最左符号。映射表示：当前处于状态、读入符号时，转入状态，并把输入头向右移一格。整套转移关系可以用状态变换图表示，其中终止状态用双圈、起始状态用带“开始”标记的箭头表示。

DFA 定义的语言

如果一个句子使得满足且，就称被接受。由定义的语言就是所有被接受的句子的集合：

例如，下面的 DFA 接受“含偶数个和偶数个 ”的串：

它的四个状态分别记录、个数的奇偶：为（偶、偶）且既是初态又是终态，其余状态对应（偶、奇）、（奇、偶）、（奇、奇）。例如串含四个、两个，均为偶数，故被接受。

不确定有限自动机（NFA）

不确定有限自动机（non-definite automata, NFA）同样是五元组，它与 DFA 的唯一区别在转移函数：

即不再是一个确定状态，而是一个状态集合：面对同一个“状态＋输入”，机器可以同时进入多个状态，也可以无路可走（取）。例如以下 NFA 接受串：

NFA 在描述上更灵活，但识别能力并不更强：任何一个被 NFA 接受的语言，都存在一个 DFA 接受它（可用数学归纳法证明）。由于二者接受的链集相同，一般情况下无需区分它们，统称为有限自动机。

正则文法与有限自动机的等价

由文法构造自动机

正则文法与有限自动机之间也有着直接对应：若是一个正则文法，则存在有限自动机，使得。构造规则如下：

正则文法	有限自动机

	，为终态
	将设为终态
开始符号	为初态
非终结符	对应状态

可以概括为一句话：非终结符变状态，终结符变边，开始符定初态，结束产生式定终态。

一个例子

给定正则文法，其中、、，构造与它等价的 NFA。

先取、、、，其中新引入的是终态。再按对应规则逐条翻译产生式：

映射	取值	依据

		无
		，

		无
		无

其中正体现了 NFA 的不确定性：读到且处于时，既可以留在（继续满足），也可以进入终态（结束于）。

这样，正则文法、正则语言与有限自动机三者就统一在了同一个框架之下——这也是形式语言理论对自然语言处理最基础的一点启示：语言、生成语言的规则、识别语言的机器，是同一件事的三种表述。