【统计自然语言处理】形式语言与自动机

文章目录

1. 1. 基本概念
   1. 1.1. 图
   2. 1.2. 树
   3. 1.3. 字符串
2. 2. 形式语言
   1. 2.1. 概述
   2. 2.2. 形式语法的定义
   3. 2.3. 形式语言的类型
      1. 2.3.1. 正则文法
      2. 2.3.2. 上下文无关文法
      3. 2.3.3. 上下文有关文法
      4. 2.3.4. 无约束文法
   4. 2.4. CFG识别句子的派生树表示
3. 3. 自动机理论

博客主要参考宗成庆老师《统计自然语言处理》一书第二版第三章。

害，写一系列博客的目标，一是作为读书笔记，以后自己哪块部分忘了回来翻翻就完事了；二是起到一个监督作用，毕竟作为一个懒鬼哪天看着看着书不小心就鸽了。

形式语言理论是自然语言描述和分析的基础，主要包括：
(1) 词法分析；
(2) 拼写检查；
(3) 短语识别；

基本概念

图

图的本质内容是二元关系。图又分为无向图和有向图两种。主要包括
(1) 无向图：可以直接定义为一个二元组，(ni,nj)=(nj,ni)，n表示图中的结点；
(2) 有向图：也可以定义为一个二元组，但是(ni,nj)≠(nj,ni)；
(3) 连通图：连通图是一个无向图G=(N,E)或有向图D=(N,E)，N表示节点，E表示关系。对于N中的任意两个顶点ns和nt，存在一个顶点的序列P，使得ns=n(i0),n(i1),…,n(ik)=nt均属于N，且ej=(ni(j),ni(i+1))(j=0,1,…,k-1)均属于E(对于有向图D，任意ej=(ni(j),ni(j+1))均属于E)。P也被称为图G或D的一条路径或通路。
(4) 回路：即开始和终结于同一顶点的通路成为回路。

树

一个无回路的无向图称为森林。一个无回路的连通无向图称为树（或自由树）。如果树中有一个结点被特别地标记为根节点，那么，这棵树成为根树。
从逻辑结构上讲，树是包含n个结点的有穷集合S(n>0)，且在S上定义了一个关系R，R满足以下三个条件：
(1) 有且仅有一个结点t0∈S，该结点对于R来说没有前驱，结点t0称作树根；
(2) 除了结点t0以外，S中的每个结点对于R来说，都有且仅有一个直接前驱；
(3) 除了结点t0以外的任何结点t∈S，都存在一个结点序列t0,t1,…,tk，使得t0为树的根，tk=t，有序对<t(i-1),t>∈R(1≤i≤k)，则该结点称为从根结点t0到结点t的一条路径。

字符串

“连接”和“闭包”是字符串操作中的两种基本运算。

(1) 字符串连接：假设x,y是字符合集中的字符串，则xy即为两个字符串的连接。
eg. x=abc,y=cba,xy=abccba
(2) 符号串集合的乘积：设A,B是字符表上的符号串的集合，则A和B的乘积定义为：AB={xy|x∈A,y∈B}
(3) 闭包运算：字符表上的符号串集合V的闭包定义为：V*=V0 U V1 U V2 U …,V+ = V1 U V2 U…,V+ = V* - {ε}。
eg. 如果V={a,b}，那么，根据定义有：
V*={ε,a,b,aa,ab,bb,ba,aaa,…}
V+={a,b,aa,ab,bb,ba,aaa,…}

一般地，通常用|x|表示字符串的长度，即字符串x中包含字符的个数。

形式语言

概述

乔姆斯基把语言定义为：按照一定规律构成的句子和符号串的有限或无限的集合。

一般地，描述一种语言可以有三种途径：
(1) 穷举法：枚举出语言中所有的句子，但这种方法仅适合于句子数目有限的语言。
(2) 文法(产生式系统)描述：语言中的每个句子用严格定义的规则来构造，利用规则构造语言中合法的句子。文法用来精确地描述语言及其结构，用文法来定义语言的优点：由文法给予语言中的句子以结构，各成分之间的结构关系清楚、明了。
(3) 自动机法：通过对输入的句子进行合法性检验，区别哪些是语言中的句子，哪些不是语言中的句子。对于自动机，识别一个字符串是否属于该语言相对简单，但是很难描述语言的结构。

因此，自然语言处理中的识别和分析算法，大多兼取二者之长。

形式语法的定义

形式语言是用来精确地描述语言（包括人工语言和自然语言）及其结构的手段。形式语言学也称代数语言学。

(1)形式语法:形式语法就是一个四员组G=(N,∑,P,S),其中，N是非终结符的有限集合(有时也称为变量集或句法种类集)；∑是终结符号的有限集合。V=N U ∑ 称为总词汇表；P是一组重写规则的有限集合（一组字符串不断地应用重写规则，就可以得到另外一个字符串；利用不同的规则来生成字符串同理。）P是一组重写规则的有限集合；S∈N称为句子符或初始符。

(2)推导:如果αβγ是(NU∑)*中的符号串，且β->δ是P中的一个产生式，那么αβγ=>αδγ.
如果每次推导都只修改最左边的那个非终结符，这种推导称为“最左推导”。反之，称为最右推导。
eg.给定文法G(S)的一组规则：

则字符串”关于鲁迅先生的文章”的最左推导为：

同理，字符串”关于鲁迅先生的文章”的最右推导为：

(仿佛回到大一被离散数学支配的恐惧（后面要抽时间安排再过一遍离散数学了…

(3)句子:文法G=(N,∑,P,S)的句子形式（句型）通过如下递归方式定义：
a. S是一个句子形式；
b. 如果γβα是一个句子形式，且β->δ是P中的产生式，那么， γδα也是一个句子形式。
由文法G生成的句子的合集，记作L(G):

形式语言的类型

在乔姆斯基的语法理论中，文法被划分为4种类型：3型文法，2型文法，1型文法，0型文法，分别对应的是正则文法，上下文无关文法，上下文相关文法和无约束文法。

正则文法

如果文法G的规则集P中规则均满足如下形式：A->Bx或A->x，其中，A,B∈N，x∈∑，则称该文法G为正则文法，或称3型文法。
eg. G＝（N，Σ，P，S），其中，N＝{S，A，B}，Σ＝{a, b}, P：
（1）S->aA
（2）A->aA
（3）A->bbB
（4）B->bB
（5）B->b
该文法形式上似乎不满足上述正则文法定义的条件（第3条规 则），但规则（3）可以改写成如下两条规则： A->bB′ B′->bB
因此，该文法修改后为右线性正则文法，它所识别的语言为：

(有这么一瞬间我怀疑我在看编译原理…

上下文无关文法

如果文法G的规则集P中所有规则均满足如下形式：A->α，其中，A∈N，α∈(NU∑)*,则称文法G为上下文无关文法（Context-free grammer,CFG）,或称2型文法。
eg. G＝（N，Σ，P，S），其中，N＝{S，A，B，C}，Σ＝{a, b, c}，P：
（1）S->ABC
（2）A->aA|a
（3）B->bB|b
（4）C->BA|c
显然，该文法为上下文无关文法，可识别的语言为:

从定义可以看出，2型文法比3型文法少了一层限制，其规则右端的格式没有约束。也就是说，规则左部的非终结符可以被改写成任何形式。

上下文有关文法

如果文法G的规则集P中所有规则满 足如下形式：αAβ→αγβ，其中，A∈N，α，β，γ∈（NUΣ）*，且γ至少 包含一个字符，则称文法G为上下文有关文法（context-sensitive grammar, CSG），或称1型文法。
从上述定义可以看出，字符串αAβ中的A被改写成γ时需要有上文语 境α和下文语境β，这体现了上下文相关的含义。当然，α和β可以为空字 符ε，如果α和β同时为空时，1型文法变成了2型文法。也就是说，2型文 法是1型文法的特例。因此，1型文法可识别的语言集合比2型文法可识 别的语言集合更大。

eg. G＝（N，Σ，P，S），其中，N＝{S，A，B，C}，Σ＝{a, b, c}，P：
（1）S->ABC
（2）A->aA|a
（3）B->bB|b
（4）BC->Bcc
根据第（4）条规则可以断定该文法为上下文有关文法，所识别的语言为:

通过这个例子我们可以看到，规则左部不一定仅为一个非终结符， 可以有上下文限制。

无约束文法

如果文法G的规则集P中所有规则满足如 下形式：α→β，其中，α∈（NUΣ）+，β∈（NUΣ）*，则称G为无约束 文法或无限制重写系统，也称0型文法。

根据上述定义我们不难看出，从0型文法到3型文法，对规则的约束 越来越多，每一个正则文法都是上下文无关文法，每一个上下无关文法 都是上下文有关文法，而每一个上下文有关文法都可以认为是0型文 法。因此，从0型文法到3型文法所识别的语言集合越来越小。如果用 G0、G1、G2和G3分别表示0型、1型、2型和3型文法，那么，

我们约定，如果一个文法的产生式集合P中，有分属于不同类型文 法的产生式，则把属于包含最广类型文法的那条产生式所属的类型作为 这个文法的类型。比如说，某个文法的全部规则分别属于1型文法、2型 文法和3型文法，则我们称这个文法为1型文法。同理，如果一种语言能 够由几种文法所产生，则把这种语言称为在这几种文法中受限制最多的 那种文法所产生的语言。

CFG识别句子的派生树表示

一个上下文无关文法G＝（N，Σ，P，S）产生句子的过程可以由派 生树表示。派生树也称语法树（syntactic tree），或分析树（parsing tree）、推导树等。派生树的构造步骤如下：
（1）对于任意x∈N∪Σ，给一个标记作为结点，令文法的初始符号S作为树的根结点；
（2）如果一个结点的标记为A，且至少有一个除它自身以外的后裔，那么A∈N；
（3）如果一个结点的标记为A，它的k（k＞0）个直接后裔结点按 从左到右的顺序依次标记为A1，A2，…，Ak，则A->A1，A2，…，Ak一定是P中的一个产生式。
所以，句子 “关于鲁迅先生的文章”对应的派生树如下所示：

如果文法G对于同一个句子存在两棵或 两棵以上不同的分析树，那么，该句子是二义性的，文法G为二义性文法。
如果将文法G（S）稍微修改一下，增加一条规则S→PP Aux NP，那么，规则集包含如下规则：
S->PNP|PP Aux NP PP->PNP
NP->NN|NP Aux NP P->关于
NN->鲁迅|文章 Aux->的
所以，”关于鲁迅先生的文章”还有另外一种分析树：

因此，增加规则后的文法将变成二义性文法。

自动机理论

自动机是一种理想化的”机器”，它只是抽象分析问题的理论工具，并不具有实际的物质形态。它是科学定义的演算机器，用来表达某种不需要人力干涉的机械性验算过程。根据不同的构成和功能，自动机分成以下4种类型：有限自动机(finite automata,FA),下推自动机（push-down automata,PDA）,线性界限自动机（linear-bounded automa）和图灵机（Turing machine）。

（我真的觉得我在看编译原理…这章内容暂时到这…
（如果后续有需要，会折回来看并补全（