欢迎转载，作者：Ling，注明出处：自然语言处理：原理简明教程02-形式语言与自动机

参考书：《统计自然语言处理（第2版）》，《形式语言与自动机理论》，《统计自然语言基础》，《自然语言处理综论》

形式语言

形式语言：最著名的是乔姆斯基

字符串：

• 定义：假定∑是字符的有限集合，一般称作字符表，它的每一个元素称为字符。由∑ 中字符相连而成的有限序列称为∑上的字符串。特殊地，丌包括任何字符的 字符串称为空串，记作ε 。包括穸串在内的∑上字符串的全体记为∑＊
• 字符串的连接：假定∑是字符的有限集合，x，y 是∑上的符号串，则把 y 的 各个符号依次写在 x 符号串之后得到的符号串称为 x 与 y 的连接，记作 xy。如：x为ab，y为cd，xy为abcd
• 符号串集合的乘积：设A、B是字符表∑上符号串的集合，则A和B的乘积定义 为AB={ xy | x ϵ A ，y ϵ B }。其中，A0={ε}。当n≥1，An=An-1A=AAn-1。 如：A={a,b}, B={c,d}则AB={ac,ad,bc,bd}
• 闭包运算：字符表∑上的符号串集合V的闭包定义为：V＊=V0UV1UV2U…， V+=V1UV2U…，V+=V＊－{ε }，例如V={a,b},V＊={ε,a,b,aa,ab,ba,aaa}
• |x|:字符串x的长度

语言：

• 定义：按照一定规律构成的句子和符号串的有限或无限的集合。
• 描述途径：
  • 穷举法
  • 文法（产生式）
  • 自动机

形式语法（文法）定义：

• 规则：α→β
• 形式语法：形式语法是一个四元组G=（N, ∑ ,P，S）
  • N：非终结符的有限集合（有时也称为变量集戒句法种类集）
  • ∑：终结符号的有限集合
  • V：总词汇表，NU∑
  • P：一组重写规则的有限集合，P={ α→β } ，其中，α、β是由V中 元素构成的串，α中至少应含有一个非终结符号；
  • S：SϵN，称为句子符号初始
• 例子《宗》：后面那个不是，因为产生式的终结符集合不对，非终结符也不对，A->A也不对

形式语法定义（几个概念）：

语言，句子和句型定义：

简单说：语言由合文法的所有结果构成，文法最后结果是句子，中间结果是句型

文法难点：

• 给出语言L，怎样构造出产生L的文法G？
• 给出一个字符串，怎样验证它是语言L(G)的合法句子？

文法构成：

• 没有直接方法，依赖亍构造者的经验
• 大型的语言其构造文法非常复杂
• 等价文法
• 文法的简写：叧写出推导规则即可，约定，所有的非终止符和终止符均为规则里出现 过的符叵（大写字母通常代表非终止符，小写字母戒数字代表终止符）。第一条规则 左端的符叵为初始

应用：

• 描述编程语言：C语言
• 自动生成内容：有了文法，可以自动生成相应内容
  • 自动评语系统
  • 自动生成古诗词
  • 自动股评
  •  

乔姆斯基提出的四种形式文法

正则文法（3型文法）：如果文法G的规则集P中所有规则均满足以下形式：A→Bx， A→x，

其中A、BϵN，xϵ∑，则称该文法G为正则文法。

• 特点：出Bx或者x，不能只出A,B这种属于N非终结符的
• 左线性正则文法：规则右部的非终结符号（如果有的话）出现在最左边。
• 右线性正则文法：规则右部的非终结符号（如果有的话）出现在最右边。形式为A→xB
• 实例： 

上下文无关文法（2型文法）：如果文法G的规则集P中所有规则均满足如下形式： A→α，其中，AϵN，αϵ（NU∑）＊，则称文法G为上下文无关文法。

• 特点：产生式右边可以有纯非终结符
• 实例：

上下文有关文法（1型文法）：如果文法G的规则集P中所有规则均满足如下形式： αAβ→αγβ，其中，AϵN，α、β、γϵ（NU∑）＊，且γ至少包含一个字符，则称文法G 为上下文有关文法。

• 特点：允许产生式左边有多个非终结符

无约束文法（0型文法）：如果文法G的规则集P中所有规则均满足如下形式：α→β， 其中，αϵ（NU∑）+，βϵ（NU∑）＊，则称文法G为无约束文法。

四者关系：

四种自动机

有限自动机（Finite Automata,DFA）：即有限个状态

• 确定有限自动机（Definite Finite Automata,DFA）：每个输入，对应的转移的状态唯一

• 不确定有限自动机（Non- Definite Automata, NFA）：每个输入，对对应的转移状态不唯一，但是有限

• NFA和DFA等价，可以将NFA转换为DFA
• 正则文法与有限自动机对应，可以互相转换

下推自动机（Push-Down Automata, PDA）：即到下一个状态不仅和当前输入相关，还和存储器栈顶元素有关，每次从栈顶pop一个，结合当前输入，判断下一个状态，同时入栈相应的元素，到了终点或者栈空结束

• 两种接受标准等价
• 下推自动机等价于上下文无关文法，可以互相转换

• 实例

线性界限自动机（Linear-Bounded Automata, LBA）

图灵机(Turing Machine, TM)

自动机对比：

文法与自动机关系：

自动机应用

单词纠错：

• 论文：

• 原理：首先将所有标准单词建立树，然后根据输入的单词，和树上节点比较，看编辑距离在规定的误差内，找到这么一个路径，作为纠正的单词，可能多个。但是单纯靠编辑距离，计算量会比较大，于是提出了cut-off编辑距离，减少计算。

• 编辑距离：X为标准，Y为输入，Y变成X需要的最小修改次数，用DP求解

• Cut-off编辑距离：假设标准Y为repo，X为输入串reprter，允许误差编辑为t=2，X长m=7,Y长n=4，则设置l=n-t=2,u=n+t=6,以X开头，2-6的长度都和Y求ed，把最小的作为X和Y的cut-off ed。因为ed肯定大于cut-off ed，所以实际上用cut-off ed作为剪枝标准是更agressive的做法，也就是，如果cut-off都不满足，更别说ed了，先要满足cut-off ed，再看看是否满足ed

• 步骤：假设t=1，要在树上找到和ababa匹配的结果，左边是自动机。[]中的数为当前节点构成的Y和X的cut-off ed,例如：Y=b, X=ababa,cut-off ed =1 套上面我说的那个方法得到的，如果cut-off ed大于2，不用往后走，重线圈的是最后的结果，也就是X可能纠正的单词

词性消解：

• 词性标注：
  • 目的：更好理解句子成分
  • 著名标注集：斯坦福，宾大，北大

• 消解论文：
  • 目的：一个词可能标注多种词性，最后确定某个词性，比如like，可能动词也可能介词，如果确定是介词，就知道其意思是：像

• 步骤：
  • 问题：shot是动词，在by前，应该可以确定是被动动词

• 规则：

• 状态机：解释图5，by经过后，要把vbd改成vbn。步骤，先根据规则，写出所有状态机，最后得到复杂的一个状态机，然后把不确定状态机转成确定状态机，以后输入一个句子，就可以进行词性消解。