形式语言与自动机理论

概述：

乔姆斯基（Noam Chomky）曾经把语言定义为：按照一定规律构成的句子和字符串的有限或无限的集合。也有把语言看成一个数学系统....深奥，看不懂～～～
总之呢，描述一种语言大致有如下三种途径：

穷举法
文法：每个句子都由严格定义的规则来构造，基于规则产生句子。我这里理解为我们语文中的语法规则。什么主谓宾之类的～～～
自动机法：通过对输入的句子进行合法性监测区别哪些是语言中的句子，哪些不是。

形式语言

也称之为代数语言学，用来精确的描述语言及其结构的手段。
形式语法的定义这里就不阐述了，可以参考wiki。文法表示为： $G=(N,E,P,S)$ 。
乔姆斯基将文法分发分为如下四种：

正则文法
上下文无关文法
上下文相关文法
无约束文法

自动机

理论太难懂了..... 简单说就是由5组元素组成，字符集，状态集，状态转移，起始，末尾。5个要素。 $M =(E,Q,\delta ,p_0,F)$ ， $\delta(q,a) = q'$

状态转移

文法与自动机之间的关系

文法中的非终结符可以理解为自动机中的字符集，终结符理解为状态集，状态转移可以用规则转换得到。

自动机的应用：编辑距离：从一个字符串转变到另一个字符串最少步骤（插入，删除，交换，修改）。场景应用：拼写纠错～。

拼写纠错

字母表A上的字母构成的所有合法单词都是自动机中的一条路径（有向图）。即一条路径上从起始状态到终止状态连起来的字符串就是合法拼写。目标：寻找有向图中编辑距小于给定阈值t的所有路径。这些路径就是满足阈值t的相似拼写集合。

当然，当数据量大的话，为了提高搜索速度，则会采取剪枝操作。

cuted（X[m],Y[n]） = \min_{l<i<u}{ ed(X[i],Y[n])}

其中

l = \max(1,n-t),u = \min(m,n+t)

t

是设定的最小编辑距离阈值～也就是在子串中已经超过阈值了，那就没必要继续往下进行图搜索了，回溯进行其他分支。

编辑距离

例如：ed（hanzhou，hangzhou） = 1，需要进行一次插入操作。
主要思想：判断当前是需要插入，交换，还是修改使得修改次数最小。
三种情况：
(1) $ed（X{[i+1]},Y{[i+1]}） = ed（X{[i]},Y{[i]}）$ ,当 $X_{i+1} = Y_{i+1}$ 。
(2) $ed（X{[i+1]},Y{[i+1]}） =1 + min\{ed（X{[i-1]},Y{[i-1]}）,ed(X{[i]},Y{[i+1]}）,ed(X{[i+1]},Y{[i]}）\}$ ,当 $X_{i} = Y_{i+1}，X_{i+1} = Y_{i}$ 执行交换操作
(3) $ed（X{[i+1]},Y{[i+1]}） =1 + min\{ed（X{[i]},Y{[i]}）,ed(X{[i]},Y{[i+1]}）,ed(X{[i+1]},Y{[i]}）\}$ ,其他情况

简单解析：

min 操作就是判断前一步骤是修改，还是删除，还是插入。ed(X{[i]},Y{[i+1]}）是插入操作，ed(X{[i+1]},Y{[i]})删除操作,ed（X{[i]},Y{[i]}）则是修改操作。

附页

常见符号解释

标记代码	标记名称
ROOT	要处理文本的语句
IP	简单从句
NP	名词短语
VP	动词短语
PU	断句符，通常是句号、问号、感叹号等标点符号
LCP	方位词短语
PP	介词短语
CP	由‘的’构成的表示修饰性关系的短语
DNP	由‘的’构成的表示所属关系的短语
ADVP	副词短语
ADJP	形容词短语
DP	限定词短语
QP	量词短语
NN	常用名词
NR	固有名词
NT	时间名词
PN	代词
VV	动词
VC	是
CC	表示连词
VE	有
VA	表语形容词
AS	内容标记（如：了）
VRD	动补复合词
CD	表示基数词

来源原文：https://blog.csdn.net/lihaitao000/article/details/51812618