放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

第3章 形式语言与自动机

目录

3.1 基本概念

3.1.1 图

无向图、有向图、连通图和回路。

3.1.2 树

森林:无回路无向图。

树:无回路连通无向图。

根树:有根节点的树。

3.1.3 字符串

Σ:是字符表。

字符串:由Σ中字符相连而成的有限序列被称之为Σ 上的字符串(或称符号串,或称链)。

空串:特殊地,不包括任何字符的字符串称为空串,记作ε。

字符串长度:符号串中符号的个数。符号串x的长度用|x|表示。|ε| = 0。

Σ*:包括空串在内的Σ上的全部字符串。

字符串连接:xy=把y的各个符号写在x的符号之后得到的符号串。

xn:把x自身连接n次得到的符号串,即z=xx…x (n个x), 称为x的n次方幂,记作xn

字符串集合乘积:将来自两个字符串的集合的字符串按顺序连接起来。

闭包运算:字符表Σ上的所有可能的字符串组成一个集合V。

正闭包:V+ = V* – {ε},即闭包减去空串。

3.2 形式语言

3.2.1 概述

3.2.2 形式语法的定义

形式语法形式语法是一个4元组G=(N, Σ, P, S), 其中N 是非终结符(通常大写,如A、B)的有限集合;Σ是终结符(通常小写,如x、a、b)的有限集合,N ∩ Σ = Φ;V = N ∪ Σ 称总词汇表;P 是一组重写规则的有限集合:P={ α → β },其中,α,β 是V 中元素构成的串,但α 中至少应含有一个非终结符号;S ∈ N,称为句子符或初始符这有点像编译原理?编程语言就是自然语言的模型……吧。

推导β->γ表示αβγ可以转换到αδγ,这种转换记作

按非平凡方式派生表示至少推导一次。

派生表示推导0或正数次。

最左推导:每步推导中只改写最左边的那个非终结符。

最右推导:每步推导中只改写最右边的那个非终结符,也称规范推导。

句子:由初始符按照重写规则推导出来的句子形式。其中不含非终结符的句子形式称为G 生成的句子。

语言:由文法G 生成所有句子,记作L(G)。

3.2.3 形式语法的类型

分为4种类型:3、2、1、0型文法,分别对应:

1.正则文法

正则文法:所有规则均推导出开头或结尾为终结字符的字串(自己理解的)。如果文法G=(N, Σ, P, S) 的P 中的规则满足如下形式:A → B x,或A → x,其中A, B ∈ N,x ∈ Σ,则称该文法为正则文法(简写为FSG)或称3型文法(左线性正则文法)。(如果A → x B,则该文法称为右线性正则文法。)

2.上下文无关文法

上下文无关文法:所有规则的左侧和推导结果不限于N或Σ,其实就是正则文法阉割掉限制。如果P 中的规则满足如下形式:A → α,其中A ∈ N,α ∈ (N ∪ Σ)*,则称该文法为上下文无关文法(CFG)或称2 型文法。

3.上下文有关文法

推导规则左右侧的不同之处体现在字串的中间,就是生活常识里的上下文相关了。如果P 中的规则满足如下形式: α A β → α γ β,其中A ∈ N,α, β, γ ∈  (N ∪ Σ)*,且γ 至少包含一个字符,则称该文法为上下文有关文法(CSG)或称1 型文法。

规则左侧不一定仅仅是一个N,并且右侧一定不短于左侧。

4.无约束文法

无约束文法:正闭包中的字串推导出闭包字串。如果P 中的规则满足如下形式: α → β,α, β 是字符串,则称G 为无约束文法,或称0型文法。

总结

文法的编号体现了文法的约束程度之大,L(G0) ⊇ L(G1) ⊇ L(G2) ⊇ L(G3)。文法类型取决于全部规则中编号最小的那一种。

3.2.4 CFG 产生的语言句子的派生树表示

自己理解的是按照S在左侧的规则从大到小拆成树,这让我想起了现代汉语课上的短语类型分析。

二义性文法:一个文法G对应两颗或以上的分析树。比如“关于鲁迅的文章”。

3.3 自动机理论

自动机是概念上的演算机器。

3.3.1 有限自动机

确定性有限自动机

确定的有限自动机(Definite Automata, DFA) M 是一个五元组:

M = (Σ, Q, δ, q0, F)

其中,

Σ 是输入符号的有穷集合;

Q 是状态的有限集合; 

δ 是Q 与Σ 的直积Q × Σ 到Q (下一个状态) 的映射。它支配着有限状态控制的行为,有时也称为状态转移函数。

q0 ∈ Q 是初始状态;

F 是终止状态集合,F ⊆ Q;

我觉得可以把DFA想象成一个单放机,插入一盘磁带,随着磁带的转动,DFA读取一个符号,依靠状态转移函数改变自己的状态,同时磁带转到下一个字符。

不确定的有限自动机:

(Non-definite Automata, NFA)不确定的有限自动机M 是一个五元组

M = (Σ, Q, δ, q0, F)

其中,

Σ 是输入符号的有穷集合;

Q 是状态的有限集合; 

δ 是Q与Σ的直积Q×Σ 到Q的幂集2Q 的映射。

F 是终止状态集合,F ⊆ Q;

q0 ∈ Q 是初始状态;

两者的不同在于,DFA接受一个符号之后的状态是唯一的,而NFA则是一个集合中的某个。

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

NFA 与DFA 的关系设L 是一个被NFA 所接受的句子的集合,则存在一个DFA,它能够接受L 。(用数学归纳法很好证明)

3.3.2 正则文法与有限自动机的关系

一定存在一个FA可以定义正则文法的语言:若G = (VN, VT, P, S ) 是一个正则文法,则存在一个有限自动机M = (Σ, Q, δ, q0, F),使得:T(M) = L(G)。

FA M的构造方法,M = (Σ, Q, δ, q0, F)

Σ为G的Σ

Q为G的N和{T}的并集(T是一个概念上虚拟的非终止符,代表一个终止状态)

如果P中有产生式B->a,则加入将T加入映射δ(B,a),如果P中有产生式B->aC,则将C加入映射δ(B,a)。最后对每一个终止符a∈VT δ(T,a) = ∅

q0毫无疑问为S

如果P中有产生式S->e(初始直接终结)则F={S,T}(将S看做终止状态)否则F={T}。

一定存在一个正则文法可以定义FA的语言M = (Σ, Q, δ, q0, F) 是一个有限自动机,则存在正则文法G = (VN, VT, P, S ) 使L(G)=T(M)。

3.3.3 上下文无关文法与下推自动机

PDA:下推自动机(Push-Down Automata, PDA)可以表达成一个7元组:

M = (Σ, Q, Γ, δ, q0, Z0, F)

其中,

Σ 是输入符号的有穷集合;

Q 是状态的有限集合;

Γ 为下推存储器符号的有穷集合;

δ 是从Q×(Σ∪{ε})×Γ 到Q×Γ* 的子集的映射。

q0 ∈ Q 是初始状态;

Z0∈Γ 为最初出现在下推存储器顶端的开始符号;

F 是终止状态集合,F ⊆ Q;

映射关系δ(q, a, Z) = {(q1, γ1), (q2, γ2), …, (qm, γm)}表示当前状态q,接受字符a,自动机可能进入状态qi,并且栈顶符号弹出,γm入栈。没看出来这个概念有什么用,也没看出来跟上下文无关文法有什么关系。

图灵机和线性界限自动机似乎更加看不出来有什么用处,老毛病又犯了,你不告诉我它有什么用,我就不学它。万一它真的有用,我随时再学就行了。

3.4 自动机在自然语言处理中的应用

3.4.1 单词拼写检查

关于字符串编辑距离的实现

关于有限自动机找出正确字串,修改图的深度优先搜索算法即可,弄个stack,注意剪枝就行。

3.4.2 单词形态分析

有限状态转换机:(finite state transducer, FST)粗略地讲,有限状态转换机与有限自动机(或有限状态机)的区别在于:FST在完成状态转移的同时产生一个输出,而FA(或FSM)只实现状态转移,不产生任何输出。

在达到状态heav的时候,再接受y的话结束,再接受i的时候输出heavy同时接受空输入,接着输出+然后接受后缀er或est等等。

3.4.3 词性消歧

其实我看完之后觉得这丫就是个Tire树吧……

第三章读后感

概念很多,如果不准备搞学术的话千万不要看;否则千万要整理个重点出来,不然看不懂论文。实际工业生产中很多司空见惯的东西在学术上有种种“学名”,懂一点总是好的,至少可以以学名作为关键字上Google查资料或者问别人。

以后可能不会写这样的博文了,因为公式太难打了……正在考虑买个Note,用SPen写笔记的话应该挺不错。正巧没有手机用,买个3G的Note 2014 Edition还能打电话。可惜国产的TD-SCDMA总是不被国外认可,导致我的移动卡不能上3G

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 第3章 形式语言与自动机

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的作品

HanLP自然语言处理包《自然语言处理入门》