自然语言是思维的载体，逻辑是思维的规律和规则，由此可以推出自然语言是逻辑的载体，
将形式逻辑在形式上符号化、数学化后，即是数理逻辑
形式语言既是形式逻辑的载体，又是数理逻辑的载体
数学函数是对应关系，反映事物之间的映射规则，是对关系的一种限制
有些问题不容易找到程序式的过程或步骤，主要是不易梳理出顺序式的算法步骤，

形式语言



1.形式语法定义

无论哪种语言都是句子和符号串的集合，描述一种语言的三种方法： 

1. 穷举法：把语言中的所有句子都枚举出来。 

2. 文法描述：语言中的每个句子用严格定义的规则来构造，利用规则生成语言中合法的句子。（用来精确地描述语言和其结构） 

3. 自动机法：通过对输入的句子进行合法性检验，区别哪些是语言中的句子，哪些不是。（用来机械地刻画对输入字符串的识别过程）

定义（形式语法）：一个四元组G=（N，∑，P，S），其中N是非终结符的有限集合；∑是终结符号的有限集合，N∩∑=∅；V=N∪∑称为总词汇表；P是一组重写规则的有限集合：P={α->β}，其中α，β是由V中元素构成的串，但是α中至少应含有一组非终结符号；S∈N称为句子符或初始符。

附录【字符串的闭包运算】字符表∑上的符号串集合V的闭包定义为：V*=V0∪V1∪V2∪….，V+=V1∪V2∪….(或 V*-{ε})。 

e.g.: V={a,b},则 V*={ ε,a,b,aa,ab,bb,ba,aaa,…} V+={a,b,aa,ab,bb,ba,aaa,…}

定义（推导）：设G=（N，∑，P，S）是一个文法，在(N∪∑)*上定义关系 =G=> 为： 

如果αβγ是 (N∪∑)*中的字符串，且β->δ是P中的一个产生式，那么αβγ =G=> αδγ。

按非平凡方式派生 =G+=>：表示=G=>的传递闭包，即(N∪∑)*上的符号串ξi到ξi+1（i>=0）至少经过一步推导或派生。 
派生=G*=>：表示=G=>的自反或传递闭包，即由(N∪∑)*上的符号串ξi到ξi+1经过n（n>=0）步推导或派生。 

【其中最右推导为规范推导】

定义（句子）文法G=（N，∑，P，S）的句子形式通过如下递归方式定义：1）S是一个句子形式；2）如果γβα是一个句子形式，且β->δ是P中的产生式，那么γδα也是一个句子形式。 

对于文法G，不含非终结符的句子形式成为G生成的句子。由文法G生成的语言（或称G识别的语言）是指G生成的所有句子集合，记作 L(G)={x|x∈∑，S=G*=>x}。

2.形式语法的类型



正则文法（3型文法）

定义（正则文法）：如果文法G的规则集P中所有规则均满足如下形式：A->Bx，或A->x，其中A,B∈N，x∈∑，则称该文法G为正则文法。

A->Bx为左线性正则文法 

A->xB为右线性正则文法



上下文无关文法（2型文法）

定义（上下文无关文法）：如果文法G的规则集P中所有规则均满足如下形式：A->α，其中A∈N，α∈(N∪∑)*，则称文法G为上下文无关文法（CFG，context-free grammar）。 




上下文有关文法（1型文法）

定义（上下文有关文法）：如果文法G的规则集P中所有规则满足如下形式：αAβ->αγβ，其中A∈N，α，β，γ∈(N∪∑)*，且γ至少包含一个字符，则称文法G为上下文有关文法（CSG，context-sensitive grammar）。 

从定义可以看出，字符串αAβ中的A被改写成γ时需要有上文语境α和下文语境β。当α和β为空字符 ε时，1型文法变成了2型文法，即2型文法是1型文法的特例。 


通过这个例子看出，规则左部不一定仅为一个非终结符，可以有上下文限制，但规则右端的长度不小于规则左部的长度。 

因此该文法另一种定义：如果文法G为上下文有关文法，当且仅当x->y，x∈(N∪∑)+，y∈(N∪∑)*，并且|y|>=|x|。



无约束文法（0型文法）

定义（无约束文法）：如果文法G的规则集P中所有规则满足如下形式：α->β，其中α∈(N∪∑)+，β∈(N∪∑)*，则称G为无约束文法或无限制重写系统。 




3.CFG识别句子的派生树表示

一个上下文无关文法G=（N，∑，P，S）产生句子的过程可以由派生树（语法树/分析树/推导树）表示。 

派生树构造步骤： 


定义（二义性文法）：如果文法G对于同一个句子存在两棵或者两棵以上不同的分析树，那么该句子是二义性的，文法G为二义性文法。 





自动机理论



有限自动机（FA，finite automatic）

1.确定性有限自动机（DFA，definite automata）

定义（确定性有限自动机）DFA M是一个五元组：M=（∑，Q，δ，q0，F）。其中∑是输入符号的有穷集合；Q是状态的有限集合；q0∈Q是初始状态；F⊆Q是终止状态集合；δ是Q与∑的直积Q×∑到Q（下一个状态）的映射，它支配着有限状态控制的行为，有时也称为状态转移函数。 


原理：处在状态q∈Q中的有限控制器从左到右依次从输入带上读入字符。开始时有限控制器处在状态q0，输入头指向∑*中一个链的最左符号。映射δ(q,a)=q’ （q,q’∈Q，a∈∑）表示在状态q时，若输入符号为a，则自动机M进入状态q’并且将输入头向右移动一个字符。 

定义（DFA接受的语言）如果一个句子x对于有限自动机M有δ(q0,x)=p，p∈F，则称句子x被M接受。被M接受的句子的全集称为由M定义的语言，或称M所接受的语言，记作T(M)={x | δ(q0,x)∈F}。

用状态图描述映射δ，δ(q,a)=q’的状态转换图如下： 


状态转换图的构造方法：每个状态作为一个节点，用圆圈表示。如果处在状态q并接受输入符号a∈∑时的DFA转移到q’状态，那么画一条有向弧从状态q到达状态q’，标记为a。终止状态用双圈表示，开始状态用带“开始”说明的箭头标出。 


该DFA识别的语言为“所有0、1构成的至少包含一个0的字符串”。

2.不确定性有限自动机（NFA，non-definite automata）

定义（不确定的有限自动机）NFA M是一个五元组：M=（∑，Q，δ，q0，F）。其中∑是输入符号的有穷集合；Q是状态的有限集合；q0∈Q是初始状态；F是终止状态集合，F⊆Q；δ是Q与∑的直积Q×∑到Q的幂集2Q的映射。

NFA与DFA的重要区别是：在NFA中δ(q,a)是一个状态集合，而在DFA中δ(q,a)是一个状态。根据定义，对于NFA M有映射：δ(q,a)={q1,q2,…,qk},k>=1。 

即NFA M在状态q时，接受输入符号a时，M可以选择状态集q1,q2,…,qk中任何一个状态作为下一个状态，并将输入头向右边移动一个字符的位置。

定义（NFA接受的语言）如果存在一个状态p，有p∈δ(q0,x)且p∈F，则称句子x被NFA M所接受。被NFA M接受的所有句子的集合称为NFA M定义的语言，记作T(M)={x | p∈δ(q0,x) 且 p∈F}。

定理：设L是被NFA所接受的语言，则存在一个DFA，它能够接受L。



3.正则文法与自动机的关系

重要结论：对于任意一个正则文法所产生的语言，总可以构造一个确定的有限自动机识别它。（即对任意一个正则文法，总可以构造一个确定的有限自动机） 
两个定理 

G->FA 


FA->G 


e.g.: 



下推自动机（PDA，push-down automata）

下推自动机（PDA）可以看成是一个带有附加下推存储器的有限自动机，下推存储器是一个堆栈（stack）。原理示意图如下： 


定义（PDA）不确定的下推自动机可以表达成一个七元组：M=(∑，Q，τ，δ，q0，Z0，F)。其中∑是输入符号的有穷集合；Q是状态的有限集合；τ为下推存储器符号的有穷集合；q0∈Q是初始状态；Z0∈τ为最初出现在下推存储器顶端的开始符号；F⊆Q是终止状态集合；δ是从Q×(∑∪{ ε})×τ到Q×τ*的子集的映射。



图灵机（Turing machine）

图灵机VS有限自动机， 图灵机可以通过其读写头改变输入带上的字符。

定义（图灵机）一个图灵机T可以表达成一个六元组：T=(∑，Q，τ，δ，q0，F)。其中∑是输入/输出带上字符的有穷集合，不包含空白符号B；Q是状态的有限集合；τ是输入符号的有穷集合，包含空的符号B，∑⊆τ，τ=∑∪{B}；q0∈Q是初始状态；F⊆Q是终止状态集合；δ是从Q×τ到Q×(τ-{B})×{R，L，S}子集的一个映射。其中R,L,S分别表示右移一格，左移一格和停止不动。 


线性界限自动机（linear-bound automata）

线性界线自动机是一个确定的单带图灵机，其读/写头不能超越原输入带上字符串的初始和终止位置，即线性界线自动机的存储空间被输入符号串的长度所限制。

定义（线性界线自动机）一个线性界线自动机M可以表达成一个六元组：M=(∑，Q，τ，δ，q0，F)。其中τ是输入/输出带上符号的有穷集合；Q是状态的有限集合；∑是输入/输出带上字符的又穷集合，∑⊆τ；q0∈Q是初始状态；F是终止状态集合，F⊆Q；δ是从Q×τ到Q×τ×{R,L}子集的映射。 

∑包括两个特殊符号#和$，分别表示输入链的左端和右端结束标志。 



总结

各类自动机之间的主要区别是它们能够使用的信息存储空间的差异： 

1. 有限状态自动机只能用状态来存储信息 

2. 下推自动机除了使用状态以外，还可以用下推存储器（堆栈） 

3. 图灵机等价于无约束文法 

4. 线性界线自动机可以利用状态和输入/输出带本身，因为输入/输出带没有“先进后出”的限制

一、前言
本文总结北邮计算机学院《形式语言与自动机》的学习资料，希望能帮到学弟学妹，打好基础。
从名字也能知道，这门课就是学形式化语言及其对应的自动机。这门课相对简单，知识脉络十分清晰。总结一下就是很简单。
《形式语言与自动机》同《离散数学》的感觉其实比较像，不难，也不会花太多时间，学科结构清晰。
二、思维导图
以下是自己总结的 XMind 思维导图，可以帮助梳理知识脉络，需要自取

链接：https://pan.baidu.com/s/1h7TI9tWXqFKibtPS8urVdA

提取码：6ld7
放张图：


三、课后题
这门课在网上的资源较少，少有学校开这门课，因此课后题显得尤为重要，考试基本就是你没做过的课后题原题及其变种。
因为教材使用的是北邮自己编的教材，没有制作标准答案，只有一些网上流传的答案，不过质量还可以，除了有点丑以外，答案基本正确，不过因为版本原因，出现很多缺题现象。这里提供自己总结的课后题答案：
形式语言与自动机 第二章 课后题答案

形式语言与自动机 第三章 课后题答案

形式语言与自动机 第四章 课后题答案

形式语言与自动机 第五章 课后题答案
四、其他学习资料
其他学习资料有限，我自己找到最好的是机械工业出版社的《形式语言与自动机导论》，作者是 Peter Linz，直接去看中文版就好。里面的例题和课后题比课程要求的要高一些，不过可以拓宽思路，考试万一遇到新颖的题目不至于脑子一片空白。
期末时候可以把期中题做一下用来复习前 2 章。
五、关于考试
因为疫情，我们只有期末考试，期中考试不了解，不过期中测试题还是有点难度的。期末考试难度较低，拿高分很简单，但要注意细节（比如起始状态能不能直接到 F）。
考试主要内容为设计自动机、文法等，这门课的考查点都很简单。要说有难度的就是设计题，但是如果设计不出来文法，也可以直接设计自动机然后转文法，还有就是 CH4 的泵浦引理（CH3 的泵浦引理出题很简单），可以多看看课后题和《形式语言与自动机导论》的泵浦引理，记住一些常见的证明思路。
以上，祝大家取得满意的成绩！

0. 写在前面

计算语言学，这种偏向工科的文科名字，又该怎么定义语言呢？语言的形式有是什么样子？怎么才能形式化语言以使得计算呢？自动机是什么东西，和图灵机有关系么？说了这么多有什么用呢？这一个个疑问，我们将会在接下来的讲解中，为大家一一介绍。



1. 语言

谈到语言，想必是仁者见仁，智者见智。从社会学角度来说，是人类最重要的交际工具，是人们进行沟通交流的主要表达方式。人们借助语言保存和传递人类文明的成果。语言是民族的重要特征之一。从生物学上讲，语言是指生物同类之间由于沟通需要而制定的具有统一编码解码标准的声音(图像)指令。而根据乔姆斯基的语言定义，则是认为，语言是按照一定规律构成的句子和符号串的有限或无限的集合。

既然可以计算，那么首先它得能够描述。当然这种描述肯定不能是原生态的，一定是要能计算的，也就是说使用数学方法来描述。一般的，一种语言有三种描述方式：

穷举法 

  这种方法就是把语言中所有的句子都枚举出来，显然只是一种理想的模型。
文法描述 

  这种方法通过严格定义的规则来构造语言中的每个合法句子，是一种生成式系统。
自动机法 

  这种方法是对一个句子进行合法性检验，当然也是通过一种逻辑推理系统，也就是自动机自动的完成整个检验过程。这是一种判别式系统。
可以说，文法描述是自上而下的从宏观到微观来描述整个语言的各个规则，而自动机则是从微观向宏观一步一步都进行合法检验后，得到最终结果。因此在自然语言处理中，基本上是兼取两者之长。

这里，我们提到了自动机，不急，我们会在接下来的部分向大家一点一点透露整个计算语言学的魅力。



2. 形式文法



2.1 形式文法的定义

形式语法是用来精确的描述语言及其结构的手段。其实说来很简单，例如α和β都是字符串，如果α能改写成β，则我们使用α→β来标记。不过，真正意义上的定义可能要严谨些：

形式语法是一个四元组G=（N,Σ,P,S），其中N是非终结符的有限集合，Σ是终结符的有限几个V=N∪Σ，称为总词汇表，P是一组重写规则的有限集合：P={α→β}，其中α，β是由V中元素构成的串，但是，α中至少应含有一个非终结符号，S∈N，称为句子符或者初始符。

另外，我们给出两个推导方式，如果每步推导中，只改写最左边的那个非终结字符，这种推导称为“最左推导”。反之，如果每次都只改写最右边的非终结符，则成为最右推导。

像汉语，偏向于左推导，而英语则偏向于右推导。 

例如：关于鲁迅的文章。 

我们第一遍就会认为是一篇关于鲁迅的文章，而不会认为是关于鲁迅文章的，我这么表述已经把歧义给分开了，使用的就是词序，这个在上一讲中就说过，汉语非常依赖词序。 

如果是英语的话： 

the article about Lu Xun

大家就可以看到，它和中文的语序是不同的，它相对于中文来讲，顺序近乎相反的。因此，是右推导的。



2.2 形式文法的类型

在乔姆斯基的语法理论中，文法被分为4大类，分别是正则文法，上下文无关文法，上下文有关文法和无约束文法。



2.2.1 正则文法

正则文法也称3型文法，正则文法是这4种文法中最为苛刻，约束最多的，从它的名字——正则就可以看出。正则文法是这样定义的，如果文法G的规则集P中所有规则均满足如下形式： 
A→Bx或A→x，其中A，B∈N，x∈Σ
则称G文法为正则文法，确切的讲，是左线性正则文法。因为规则又不的非终结符号（如果有的话）出现在最左边。同样的，如果是A→xB这种，则会被称为是右线性正则文法。



2.2.2 上下文无关文法

上下文无关文法也称2型文法，顾名思义，就是和上下文无关的，它只需要满足一条规则： 
A→α,其中A∈N，α∈（N∪Σ）∗
这也就是说，规则左侧的非终止符可以被改写为任何形式，但这和无约束规则还有有区别的，我们等到下面来看。



2.2.3 上下文有关文法

上下文有关文法也称1型文法，当然就是说，这个规则对上下文有要求： 
αAβ→αγβ,其中A∈N，α，β，γ∈（N∪Σ）∗，且γ至少包含一个字符
如果我们考虑，α和β都时空的话，就变成了上下文无关文法了。但这里，A如果被改写成γ，则需要上下文的支持，这也就是说，在上下文有关文法中，一个改写要依靠语境来完成。



2.2.4 无约束文法

无约束文法又称0型文法，它对于推导没有任何限制，只要满足下面一条规则就可以： 
α→β,其中α∈(N∪Σ)+,β∈(N∪Σ)∗
这是什么意思呢，粗鲁来讲，就是在存在的符号系统内，随便推导，没有任何限制。也就是说自己可以随便改写自己。这点在对应的自动机里表现的更为明显。



3. 自动机

自动机是一种抽象分析问题的理论工具，它不需要人力来驱动，只需要根据不同的条件进行不同的状态转移就可以自动执行，直到问题结束。自动机总共分为4种类型：有限自动机、下推自动机、线性界线自动机和图灵机。从识别语言的能力上来看，自动机与形式文法有一一对应的关系：有限自动机等价于正则文法，下推自动机等价于上下文无关文法，线性界线自动机等价于上下文有关文法而图灵机等价于无约束文法。具体是怎么对应的，我们接下来讲述。



3.1 有限自动机

有限自动机就是我们最熟悉的有限状态自动机，它和状态机很相似，状态机被广泛应用在嵌入式自动控制上，比如我们的自动贩卖机。它只需要在不同条件下，执行特定的结果，就可以了。有一个起始点，有终止点，不同节点之间可以进行相互转换。这就形成了有限自动机，不过这是确定性的有限自动机。有限自动机分为2种：一种是确定性有限自动机（DFA），一种是不确定性有限自动机（NFA）。



3.1.1确定性有限自动机

确定性有限自动机的定义是这样的： 
M=(Σ,Q,δ,q0,F)


其中，M表示的是输入符号的有穷集合，Q是状态的有限集合，q0∈Q是初始状态，F是终止状态集合。F⊆Q，δ是Q与Σ的直积Q×Σ到Q′的映射，它就是传说中的状态转移函数。这么说可能太过于抽象，我们举个例子来说。

从一个状态Q到另一个状态Q’，是在某一特定情况下的，比如，红绿灯的状态，从红灯开始，那么下一状态就是绿灯，绿灯开始，下一状态是黄灯，如果是从黄灯开始，那么下一状态就是红灯。每一次改写都会根据上一状态，确定性的选择下一状态。 



3.1.2不确定性有限自动机

而不确定性有限自动机，与确定性有限自动机的最大区别就在于，在状态转移的时候，M可以选择任一状态来进入到下一状态，就像上面提到的红绿灯一样，红灯结束了，可以是绿灯亮，还可以是黄灯亮，只要是合法的状态转移，它都可以进行改写，而不是像确定性转移，只能有一种状态转移。

但事实上，DFA和NFA能接受的语言是同样的语言，所以一般情况下无需区分他们，而这统称为有限自动机(FA)。其实如果以后量子计算机发明了以后，可能这两者就不相同了。有限自动机对应的是正则文法。



3.2 下推自动机

下推自动机（PDA）可以看成是一个带有附加吓退存储器的有限自动机，下推存储器是一个堆栈。这么说的意思就是，有限自动机，它只能根据当前一个状态决定最终的输出，而下推自动机则会根据一串状态来决定最终的改写，基本上是具有短时记忆功能，例如像我们的括号匹配之类的，这种，都是利用了栈这个特性。

同样举个例子来说，自动贩卖机这种，它就相当于一个下推自动机，它可以记忆你投币的数量金额，当你的金额达到你选购的物品的时候，就可以出货了，而且我们可以知道，通过不同的投币状态和顺序，可以购买到所有贩卖机里的物品。但是与下推自动机有一个区别的是，自动贩卖机它的累计金额其实是一个状态，只不过这个状态一直会改变，如果我们把状态定义为一个又一个硬币，变成离散的，而且每个硬币的金额不一致，你可以想象得到，那就是一个栈存储，先入后出。下推自动机是与上下文无关文法相对应的。



3.3 线性界限自动机

到了线性界限自动机的地步时，就有点开始走向可怕的地方了。它是一种确定的单带图灵机，其读写头不能超越原输入带上的字符串的初始和终止位置，即线性界限自动机的存储空间被输入符号串的长度所限制。这意思是说给定一个字符串，只准修改，不准添加删除，但是修改可以随意修改。这种机器就已经很厉害了，像现在冯诺依曼架构里，程序对于自身代码的修改，仅限于数据代码部分，也就是约定好的空间内，指定大小的数据。已经可以帮我们做很多事情。而之所以它和上下文有关文法相对应，是因为，在进行改写的时候，必须要看这个整体的上下文限制，比如你是个double类型的数据，你就只能在4字节内部随意修改，而不能编程一个8字节的数据。



3.4 图灵机

图灵机一直是一种玄乎又玄的机器，在很多人工智能的领域都提及。实际上，在这里的图灵机，就是和无约束文法相等价。也就是说，图灵机对于数据的改写是没有限制的，不仅是像上文提到的那样，可以把一个double类型的4字节数据，改写成为一个8字节的程序。甚至它也不会受到程序-数据代码的区分，它是可以改写自己代码的，而且是无限制改写，这就有点可怕了，它可以自我改写，自我进化。最终人类将无法阻止它。



3.5各种自动机的差异

上述四中自动机是有区别的一般为自下而上不断丰富自己的功能，是自己的表达能力更加强大。例如：

有限自动机只能使用状态来存储信息
下推自动机则增加了使用栈来存储信息
而线性带限自动机则可以利用输入、输出带本身来存储信息
图灵机是不需要限制，想怎么存储就怎么存。
4. 自动机在自然处理语言中的应用

前面我们提到过，在实际应用中，有限自动机又称为是有限状态机。那么有很多经典的应用场景。下面我们介绍几个常见的具体应用。



4.1 单词拼写检查

单词拼写检查中，就可以应用到有限自动机。最常见的单词拼写检查就是Word里的那个红色下划线，绿色下划线等，那就是单词拼写检查，而它的实现，就可以用有限自动机来实现。

单词拼写检查是肯定不能够使用查字典的方式来进行的，首先一个原因就在于效率，大家可以感受到，单词拼写检查近乎是实时的，而且在实现上，如果用词典的方式，即使使用KMP算法也不能很精确的判断出，它到底是手误还是确实就是这个单词。下面我们给出使用有限自动机的实现，这也是非常经典的一道ACM题。

假设Z=z1z2...zn为字母表A上的p个字母构成的字符串，Z[j]表示含有j个字符的子串。X[m]为拼写错误的字符串，其长度为m，Y[n]为与X串可能部分相同的字符串，其长度为n。那么，给定两个串X和Y的编辑距离ed(X[m],Y[n])，其计算方法为从字符串X转换到Y进行插入、删除、替换和交换两个相邻的基本单位操作所需的最少次数。

具体的算法如下： 

（1）如果xi+1=yi+1(两个串的最后一个字母相同)则：

ed(X[i+1],Y[j+1])=ed(X[i],Y[j])
（2）如果xi=yi+1，并且xi+1=yi(最后两个字符交叉相等)则：

ed(X[i+1],Y[j+1])=1+min{ed(X[i−1],Y[j−1]),ed(X[i],Y[j+1]),ed(X[i+1],Y[j])}
（3）其他情况下(xi+1≠yi+1且（xi≠yi+1或xi+1≠yi）)：



ed(X[i+1],Y[j+1])=1+min{ed(X[i],Y[j]),ed(X[i],Y[j+1]),ed(X[i+1],Y[j])}


这三个部分分别是： 

1、要修改X[i] 

2、要删除X[i+1] 

3、要在X[i+1]后插入一个Y[i+1] 

但是这里是有约束条件的，其中： 

当X的长度为0时，ed(X[0],Y[j])=j (0≤j≤n) 

当Y的长度为0时，ed(X[i],Y[0])=i (0≤i≤m) 

ed(X[-1],Y[j])=ed(X[i],Y[-1])=max(m,n)

这时候可能会说了，算到这也没看出怎么进行单词拼写检查呀？别急，如果我这么描述你也许就明白了。 

定义L⊆A∗表示我们正确的语言，t>0为编辑距离的阈值，那么，一个字符串X[m]∉L,也就是说一个字符串是误拼写的条件是，存在非空集合： 
C={Y[n]|Y[n]∈L,ed(X[m],Y[n])≤t}


也就是说至少存在一种合法的拼写，使得正确的拼写和错误的拼写的编辑距离小于阈值，我们就认定这种拼写是有可能是手误造成的。

那么为了提高搜索速度，可以把搜索空间限定在一个较小的范围内，尽早把那些编辑距离超过给定阈值t的路径剪枝。因此，设Y是一局部候选串（拼写正确），其长度为n，X是出错的输入串，其长度为m,令l=max(1,n-t),u=min(m,n+t)。那么，检出距离定义为： 
cuted(X[m],Y[n])=mined(X[i],Y[n])其中l≤i≤u
说了这么多，也没有做一下，下面我们给出具体的实现代码，供大家参考：

#include<stdio.h>
#include<string.h>
char s1[1000],s2[1000];
int min(int a,int b,int c)
{
    int tmp=a<b?a:b;
    return tmp<c?tmp:c;
}
void editDistance(int len1,int len2)
{
    int **d=new int*[len1+1];
    for(int i=0;i<=len1;i++)
        d[i]=new int[len2+1];
    int i,j;
    //这是边界条件
    for(i=0;i<=len1;i++)
        d[i][0]=i;
    //这是边界条件
    for(j=0;j<=len2;j++)
        d[0][j]=j;
    //这是正式计算
    for(i=1;i<=len1;i++)
    {
        for(j=1;j<=len2;j++)
        {
            int cost=s1[i]==s2[j]?0:1;
            int deletion=d[i-1][j]+1;
            int insertion=d[i][j-1]+1;
            int substitution=d[i-1][j-1]+cost;
            d[i][j]=min(deletion,insertion,substitution);
        }
    }
    printf("距离为:%d\n",d[len1][len2]);
    for(int i=0;i<=len1;i++)
    {
        delete[] d[i];
    }
    delete[] d;
}

int main()
{
    while(scanf("%s%s",s1,s2)!=EOF)
    {
        editDistance(strlen(s1),strlen(s2));
    }
}



4.2 单词形态分析

对于单词形态分析，则不是使用有限状态机，而是使用有限状态转换机。与有限状态机不同的是，有限状态转换及在完成状态转移的同时产生一个输出，而有限状态机只实现状态的转移，不产生任何输出。

以比较级和最高级为例，通常都是在词的尾部改变元音并且增加er或est。因此，如果单词尾部有改变后的元音，我们就会识别出它改变前的元音字母，并且给出是最高级和比较级。例如： 

heavy,heavier,heaviest

当状态机指向前面4个字符时，是没有办法区分这三个单词的，但是如果到了第5个字符i时，就可以识别出i:y,也就是原来是由y变过来的，然后再输出一个+，最后输出结尾是er还是est。最终的效果就是： 

heavier→heavy+er 

heaviest→heavy+est

具体实现的时候，一般让前缀或词根相同而后缀不同的单词共用一个有限状态转换机，共享其中的某些状态节点。在这里，我想说，这时候实现出的智能化，是依靠规则产生的，而并不是基于统计的机器学习的方法。但是这种方法仍然有效的多。



4.3 词性消歧

词性消歧是一个非常热门的研究领域，不过，在这里我们只是讲述一下很经典的算法，并且针对每个词的词性标注给出有限状态自动机的思想。

Roche和Schabes在建立了词性消歧的规则的基础上，通过构造状态转换机，来实现一种词性消歧的方法。该方法总共分为4步：

（1）将每一条词性标注规则转换成相应的状态转换机。 

（2）将上一步得到的每一条规则关联的状态转换机进行扩展变换，使其成为可以对输入句子进行全局操作的转换机。 

（3）将所有的状态转换机合并成一个。 

（4）把上一步得到的状态转换机转换成等价的确定性状态转换机。

通过这4步，就可以完成了整个词性消歧的过程。但是在词性标注的第一步就是要对句子中每个单词的词性通过查找字典来获取其可能的词性。这里，使用一种确定状态自动机，就可以在线性的事件内快速的完成词性标注，且执行时间与规则的数量和上下文的长度无关。

这里我们不具体展开讲述，大家有兴趣的可以自行查阅文献。



4.4 其他一些领域

自动机除了在上述领域上取得了不错的成绩，而且还在句法分析、短语识别、机器翻译和语音识别等方面都取得了很好的成就，大家有兴趣的可以自己去研读一下相关论文与文献，这里不一一列举了。



5. 小结

我相信，讲到这，我们可能对于计算语言学的一些概念和一些形式文法及自动机有一定的认识了，也对于自动机的一些应用有了直观的了解。在下面一章中，我们就要开始介绍语料库方面的知识了。好了，下期见！