当前位置：文档之家 › 有穷自动机的原理及应用-old

有穷自动机的原理及应用-old

  • 格式：pptx
  • 大小：1.35 MB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

编译原理 实验1 有穷自动机的构造与实现

编译原理 实验1 有穷自动机的构造与实现
return false;
}
char digitprocess(char buffer, FILE* fp)
{
int i=-1;
while((IsDigit(buffer)))
{
digittp[++i]=buffer;
buffer=fgetc(fp);
}
digittp[i+1]=\0';
return(buffer);
buffer=fgetc(fp);
}
alphatp[i+1]='\0';
return(buffer);
}
int main(int argc, char* argv[])
{
FILE *fp;//文件指针,指向要分析的源程序
char cbuffer;//保存最新读入的字符
if((fp=fopen(sourceFile,"r"))==NULL)//判断源文件是否存在
}
int main(int argc, char* argv[])
{
FILE *fp;//文件指针,指向要分析的源程序
char cbuffer;//保存最新读入的字符
if((fp=fopen(sourceFile,"r"))==NULL)//判断源文件是否存在
printf("文件%s不存在", sourceFile);
（2）无符号整型数，要求长度不超过20。
四、实验结果
1.识别标识符（以字母开始由字母和数字构成的字符串，要求长度不超过10）。
#include <stdio.h>
#include <string.h>

编译原理有穷自动机

编译原理有穷自动机

开始
求开始状态闭包
标记为False令它为C中唯一成员
C中存在尚未 被标记子集
否
N
是
Y 标记T 结束
对子集T中的每个输 入字母求U=Ia子集
U不在C中?
将U加入C中
图3-1 NFA转换成DFA原理图
运行结果
dfa的最小化利用等价关系找出状态集q上的所有最大等价状态子集即找出q的最小划分然后从各个等价子集中选取一个代表状态消去各等价子集中的非代表状态这样就实现了dfa的最小化的目的
有穷自动机的化简与确定化
组员：王勇 朱蓉 许立龙
1、设计内容及要求
• 可以使用任何语言来完成，例如：C、C++。 • 以文件方式读取自动机。 • 判断读取的自动机是确定的还是不确定的 自动机。 • 若是不确定的自动机，将自动机确定化。 • 将确定化后的自动机最小化。 • 输入测试字符串，输出测试结果
2. DFA的最小化 的最小化 利用等价关系找出状态集Q上的所有最大等价状态子集，即找出Q的最小划分， 然后从各个等价子集中选取一个代表状态，消去各等价子集中的非代表状态， 这样就实现了DFA的最小化的目的。 主要步骤： for v(q,p) ∈F×(Q-F) do 标记可区分状态表中的表项(q,p); /*p和q不可合并*/ for v(q,p) ∈F×F∪(Q-F) ×(Q-F)且q≠p do if E a∈∑，可区分状态表中的表项(δ(q,a), δ(p,a))已被标记 then begin 标记可区分状态表中的表项(q,p); 递归的标记本次被标记的状态对的关联链表上的各 个状态对在可区分状态表中的对应表项。 end else for v a∈∑ do if δ(q,a) ≠δ(p,a)且与(q,p)与(δ(q,a), δ(p,a))不是同一个状态对 then 将(q,p)放在(δ(q,a), δ(p,a))的关联链表上。

第三章有穷自动机

第三章有穷自动机

例：将图示的DFA M最小化。
a
b
6
4
a
a
a
b
a
1
ab
5a
7
b3
b
b
2 b
1、将M状态分为两个子集： P0=({1,2,3,4},{5,6,7})
2、{1,2,3,4}读入a后划为： P1=({1,2},{3,4},{5,6,7})
3、进一步划分： P2=({1,2},{3},{4},{5,6,7})
对M的状态集S进行划分的步骤：
①把S的终态与非终态分开，分成两个子集， 形成基本划分，属于这两个不同子集的 状态是可区别的。
②假定某个时候已含m个子集，记={I(1) , I(2) , …,I(m) }且属于不同子集的状态是可 区别的，再检查中的每个I能否进一步划 分，对于某个I(i) ，令I(i) ={S1,S2,…,Sk}， 若存在一个输入字符使得move(I(i) ,a)不包 含在现行的某一子集I(i)中，则将I(i)一分 为二。
若M的某些结既是初态结，又是终态结，
或者存在一条从某个初态结到某个终态结 的道路，则空字可为M所接受。
例： NFA M=({0,1,2,3,4},{a,b},f,{0},{2,4})
f(0,a)={0,3} f(2,b)={2} f(0,b)={0,1}
f(3,a)={4} f(1,b)={2} f(4,a)={4}
M’=(K, ,f,S,Z)
一个含有m个状态和n个输入字符的NFA 可表示为一张状态转换图，该图含有m个 状态结，每个结可射出若干条 箭弧与别的 结点相连接，每条弧用*中的一个字（不 一定要不同的字，且可以为空字）作标记 （称输入字），整个图至少含有一个初态 结以及若干个终态结。

投稿：有穷自动机在车辆管理系统开发中的应用

投稿：有穷自动机在车辆管理系统开发中的应用

有穷自动机在车辆管理系统开发中的应用摘要：本文利用有穷自动机理论对“企业车辆管理”的生命周期状态转化进行了形式化描述。

通过分析车辆管理的流程，得到了车辆管理所涉及的各项业务流程，并对各项业务进行了说明，使得车辆管理的业务流程更加清晰。

关键词: 有穷自动机；业务流程中图分类号：TP301.1 文献标识码：A1. 引言车辆管理是企业日常管理不可缺少的组成部分，车辆在其使用过程的现状不断发生改变，因而使车辆管理具有很强的动态化特征。

如果在系统分析阶段不能对车辆生命周期的状态变换过程做出准确、清晰的描述，将会导致运行阶段非法操作的出现，甚至会引起管理过程的混乱，造成资源的浪费。

因此，成功开发车辆管理系统的关键在于对车辆管理的全过程做出正确的分析和描述。

2. 车辆管理的有穷自动机设计通过对车辆管理系统的需求分析，将车辆管理全过程作为一个有穷自动机，,F)。

记为M=(Q,∑,δ,q(1) 将车辆在其整个使用周期中可能有的各种现状作为M的状态集Q;Q ={“在生产厂家”，“空闲待用”，“出车运输”，“事故扣押”，“故障在修”，“年检保养”，“加油站加油”，“公司加油”，“借出”，“报废”}；(2) 将现有车辆管理的有关业务处理作为M的输入字母表∑(括号中的字母为该业务处理的代号):∑={“购车（a）”，“保养完成（b）”，“送车保养（c）”，“车辆加油（d）”，“加油完成（e）”，“派车运输（f）”，“维修完成（g）”，“车辆送修（h）”，“运输途中故障送修（i）”，“运输途中维修完成（j）”，“运输途中加油完成（k）”，“运输途中加油（l）”，“事故处理完成（m）”，“发生事故或违章（n）”，“车辆报废（o）”，“借用（p）”，“还车（q）”，“借出过程报废（r）”，“运输完成（s）”}；=“在生产厂家”;(3) 将车辆“在生产厂家”状态作为设备开始状态q(4) 将车辆“报废”状态作为M的终止状态集F={“报废”}；(5) 把各项业务处理及引起的车辆状态变化作为M的从Q×∑->Q的映射δ(δ描述中，业务处理用相应的字母代号表示)，δ定义如下：δ(“在生产厂家”,a)= “空闲待用”δ(“年检保养”,b)= “空闲待用”δ(“空闲待用”,c)= “年检保养”δ(“空闲待用”,d)= “公司加油”δ(“公司加油”,e)= “空闲待用”δ(“空闲待用”,f)= “出车运输”δ(“出车运输”,s)= “空闲待用”δ(“空闲待用”,h)= “故障在修”δ(“故障在修”,g)= “空闲待用”δ(“空闲待用”,p)= “借出公司”δ(“借出公司”,q)= “空闲待用”δ(“出车运输”,i)= “故障在修”δ(“故障在修”,j)= “出车运输”δ(“出车运输”,l)= “加油站加油”δ(“加油站加油”,k)= “出车运输”δ(“出车运输”,n)= “事故扣押”δ(“事故扣押”,m)= “出车运输”δ(“故障在修”,o)= “报废”δ(“借出公司”,r)= “报废”其相应的状态转换图如图1所示：图1 车辆管理有穷自动机M状态转换图通过对图1状态转换图分析可得，车辆管理系统有如下8个业务操作：购车过程管理、运输过程管理、加油过程管理、维修过程管理、借车和还车过程管理、扣押过程管理、年检保养过程管理、车辆报废过程管理。

实验报告-有穷状态自动机

实验报告-有穷状态自动机
{ char temp=p[i][j]; //暂时存放一个确定的符号
if(temp>='A'&&temp<='Z')//非终结符号的判断条件
{
bool state=true;
for(int k=0;k<VN;k++)
{
if (temp==K[k]) //避免重复
{state=false;break;}
{ char temp=p[i][j]; //暂时存放一个确定的符号
if(!((temp>='A'&&temp<='Z')||temp==':'||temp=='='||temp=='\0'))
//终结符号的判断条件
{
bool state=true;
for(int k=0;k<VT;k++)
{
if (temp==E[k]) //避免重复
*****大学**学院学生实验报告
学号：年月日
系别
专业
计算机科学与技术
班级
姓名
课程名称
编译原理
课程类型
必修课
学时数
实验名称
从正则文法构造有穷状态自动机及运行
实验目的：
一、从正则文法构造有穷状态自动机（1）、掌握有穷状态自动机的概念、其存储表示及其与正则文法的联系。（2）、输入任意的正则文法，输出相应的有穷状态自动机。
（3）、将文法按五元组形式输出。
（4）、编写若干个函数，其中包括在规则中找出终结符号和非终结符号的函数，字符串输入及识别字符串函数，DFA和NFA的相关判断和输出函数，映射关系函数。

编译原理第三章_有穷自动机

编译原理第三章_有穷自动机
5
例 过河问题 分析（续）
初始状态：MWGC-φ；终止状态：φ-MWGC。 g
MWGC-φ
WC-MG
问题：
6
例 过河问题 状态转换图
起始 g
MWGC-φ g
g φ-MWGC
g
7
WC-MG
m
m MWC-G
w
w
c
C-MWG
c W-MGC
g
g
MGC-W c
MG-WC
w
m
c G-MWC
m
gg MWG-C
+dd. ddd;
输入符号串
数字 数字
SB
.
数字
+
A
H
-.
数字
.G
接收：若扫描完输入串， 且在一个终止状态上结 束。
数字 阻塞：若扫描结束但未 停止在终止状态上；或 者为能扫描完输入串 （如遇不合法符号）。
不完全描述：某些状态 对于某些输入符号不存 在转换。
练习：+34.567 .123 3.4.5
w
有穷自动机（FA）
数字系统：可以从一个状态移动到另一个状态；每次 状态转换，都上由当前状态及一组输入符号确定的；可以 输出某些离散的值集。
FA：一个状态集合；状态间的转换规则；通过读头来 扫描的一个输入符号串。
读头：从左到右扫描符号串。移动（扫描）是由状态 转换规则来决定的。
8
读头
一个FA的例子
(3)运行： 串f(，Q,且t1tt21)∈= Σf(，f(Qt1,t2t1∈), Σt2*)，其中Q∈K， t1t2为输入字符
17
例３
题：试证abba可为例1的DFA M所识别（所接受）。

有穷自动机与正规文法 编辑原理

单元目录第三单元～词法分析3.5 有穷自动机和正规文法1.正规文法和有穷自动机的等价性有穷自动机和正规文法的等价性,即:1.对于一个NFA M，都存在一正规文法G,使得L(G)=L(M)。

2.对于一个正规文法G，都存在一个NFA M，使得L(M)=L(G)。

2.有穷自动机和正规文法1.定理:设G=(VN ,VT,P,S)为一正规文法,则存在一有穷自动机使得L(M)=L(G);M的构造方法 :(右线性正规文法)为G的开始符号S和开始状态S1.增加一个新状态Z,作为NFA的终态;2.若G中有如A->tB的产生式,则令f(A,t)=B3.若G中有如A->t的产生式,则令f(A,t)=Z状态图如下:3.对左线性正规文法将右线性文法的“开始结点”与“终止结点”互换，且将各弧反向。

例：已知左线性正规文法为：I=>l|Il|Id解：先画出右线性文法的自动机再将“开始结点”与“终止结点”互换，且将各弧反向。

4.将有穷自动机转化成等价的正规文法：定理：已知一个有穷自动机FA M=(K,Σ,f, S , Z),则存在一个正规文法G＝（VN,VT,P,S),使得L（G）＝L（M)。

构造方法：对于函数f(A,t)=B 可写出 A→tB对于终态Z，可以增加一个产生式 A →ε5.习题给出接受下列字母表{0，1}上的语言DFA.(1)所有以00结束的字符串的集合。

（2）所有3个0的字符串的集合。

描述下列正规式所表示的语言（1）0(0|1)*0解：以0开头并且以0结尾的0、1串。

(2)(0|1)*0(0|1)(0|1)解：由0、1组成的串，且从右边开始数第三位为0。

(3)0*10*10*10*解：含3个1的0、1串.。

对下列语言分别写出它们的正规式（1）Σ＝{0,1}上含偶数个1的所有串解: (0|10*1)*（2）Σ＝{0,1}上含奇数个1的所有串解： (0|10*1)*0*10*。

有穷自动机的应用

有穷自动机
在设备管理系统中的ຫໍສະໝຸດ 用所谓“有穷自动机”是什么？
第一丶 为什么要用有穷自动机
“设备管理系统”是对设备从购入→报废整个使用 过程进行全面管理的计算机信息管理系统。设备在 其使用过程的状态不断发生改变，因而使设备管理 具有很强的动态化特征。如果在系统分析阶段不能 对设备生命周期的状态变换过程做出准确、清晰的 描述，将会导致运行阶段非法操作的出现，甚至会 引起管理过程中的混乱，造成设备信息的破坏。因 此，成功开发设备管理系统的关健在于对设备管理 的全过程做出正确的分析和描述。
第二丶怎么用自动机管理设备
(1)将设备管理全过程作为一个有穷自动机，记为M (2)将设备在其整个使用周期中可能其有的各种现状作为M的状态集K; K={“在用”，“待修”，“待废”，......} (3)将现有设备管理有关的业务处理作为M的输入字母表∑(括号中的 字母为该业务处理的代号): ∑={“待修处理(a)”，“待废申请(b)，“报失处理(k)”....} (4)将设备状态“在用”作为设备开始状态q0={“在用”}; (5)将设备的“报废”、“丢失”、“调出”、“退库”状态作为M 的终止状态集F. F= {“报废”，“丢失”，“调出”，“退库”} (6)把各项业务处理及引起的设备状态变化原则作为M的从K ×∑—〉 K的映射δ(δ描述中，业务处理用相应的字母代号表示)，δ定义如下： δ(“在用”，a ) =“待修” δ(“在用”，b ) =“待废”......
大家有什么问题？
制作人：陈沐豪 罗超靖 制作人：陈沐豪 罗超靖

第二章：有穷自动机和正规文法


上一页
下一页
退 出
10
2.3 DFA与NFA等效 由于DFA是NFA的特例，所以DFA能接受的语言必能为 NFA所接受，相反，NFA接受的语言，则能找到一个等效 的DFA接受语言。 定理2.3.1 设L(MN)是NFA MN接受的语言，则存在一DFA MD接受L(MD)，满足L(MD)＝L(MN)
上一页 下一页 退 出
12
n
可见［q1，q2，…，qn］是DFA MD的一个状态 通过对输入行ω的长度作归纳容易证明： δ D(q0D, ω )=[q1,q2,…,qn]⇔ δ (q0, ω )= {q1,q2,…,qn} 当|ω|=0时,即ω=ε,有δD(q0D,ε)=q0D, δ(q0,ε)={q0} 因为q0D＝［q0］,所以结论成立。 当|ω|≤K时，设 δD(q0D,ω)=[q1,q2,…,qｎ]⇔ δ(q0,ω)={q1,q2,…,qｎ}成立。 那么|ω|=K+1时,即:ω＝ω1a,ω1∈T*,a∈T,则 δD(q0D,ω1a)=δD(δD(q0D,ω1),a)
T(M)＝｛0,1｝ * 中的所有含偶数个0和偶数个1的句子集 合。
上一页 下一页 退 出
4
2.2不确定有穷自动机 1. NFA NFA M＝(K，∑，δ，q0，把字的输入头右移一个单 元，并选择P1 ，P2 ，…，PK 中任意一个作为下一个状 态。 把映射δ定义域扩大到K×Σ* ：当输入一个字符串 时，将δ改为δ＇。 △ δʹ(q,ε)＝｛q｝和δ(q,xa)= ∪ δ(p,a)
20
2.有ε转换NFA和无ε转换的NFA的等效 如果有ε转换的NFA M接受语言L(M)，则存 在无ε转换的NFA M1 使L(M1)＝L(M)。 证明：首先对应有ε转换的NFA M＝(Q，T，δ，q0，F) 构造无ε转换的 NFA M1＝(Q，T，δ1，q0，F1) F1＝ F∪｛q0｝ 当ε－closure(q0)含F的一个状态 F 否则 定义δ1:对任意q∈Q,a∈T则δ1(q, a)＝δ＇(q, a) 因为M1是无ε转换,对于δ1’可用δ1代替, 但要区别δ和δ’。 对字符串ω的长度进行归纳证明： δ1(q0，ω)＝δ’(q0，ω)

形式语言与自动机_课件_陈有祺第03章 有穷自动机

定义3.7 给出NFA M=(Q,∑,δ,q0 , F)，若δ(q0,x)∩F非空（ x∈∑*），则称字符串x被M接受。被NFA M接受的全体字符串称 为M接受的语言，记作L(M)。也就是 L(M)={x∣x∈∑*,且δ(q0,x)∩F非空}。
从定义3.7可知，在δ(q0,x)的众多状态中，只要有一个状态属于 终结状态集F，则x就被该NFA M接受。如对例3.4中的NFA，字 符串01001是被接受的，因为δ(q0 ，01001)={q0,q1,q4} ，而 q0∈F。但字符串010是不被接受的，因为δ(q0 ,010)={q0,q3} ，其中没有一个状态在F中。
从给定集合构造接受该集合的FA
实现上述思路的FA M1如图所示
初始状态标记为“1”，表示要么还没有读入符号，要么刚读过符号1。对 于“0”状态遇1，“01” 状态遇0，“010”状态再遇0或1的情况，上 面已经做了解释。其他情况是：“0”状态遇0，此时应当保持在“0”状 态，意味着刚读过的符号是0；再有“01”状态遇1，表示这次的期望“ 半途而废”，只能从头再来，所以转回到“1”状态。
形式语言与自动机
第三章 有穷自动机
非形式化描述 有穷自动机的基本定义 非确定的有穷自动机 具有ε转移的有穷自动机 有穷自动机的应用 具有输出的有穷自动机
有穷状态系统
指针式钟表共有12*60*60个状态
围棋共有3361个状态
电梯的控制结构
某些电子产品中的开关电路，具有n个门的开关网络有 2n种状态
分析：x∈L当且仅当把x看成二进制数时，x模5与0同余。换句话说，x 要能被5整除。例如，0，101，1010，1111等都能被5整除，而10， 11，100，110等都不能被5整除。
当二进制数x的位数向右不断增加时，它的值（换算成十进制）的增加很 有规律：x0的值等于2x，x1的值等于2x+1。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。


应用了路径压缩的DFA不再是严格意义上的DFA


与计算字典序的算法完美兼容
AC（Aho-Corasick）自动机

AC自动机与 Trie

AC自动机是基于Trie的 每个状态中有附加数据



一个 fail link 模式串集合的一个子集 因为一个模式串可能是另一个模式串的后缀


这种策略对应的算法更快，直观上看需要更多的内存，但实际上，每个状态的第 一个转移对应的这个数字总为0，可以省去，再加上对于很多自动机，状态的平均 转移数小于2，从而，需要的内存甚至更少（只有当平均转移数大于2时，这种策略 才需要更多的内存）！
路径压缩

将直线形的状态序列压缩成一个状态

序列中每个状态只有一个后续状态 除序列起始状态，其它状态都不是汇合状态 除序列末尾状态，其它状态都不是终止状态

Partition Refinement

Hopcroft 算法伪代码
P := {F, Q \ F }; // \ 表示集合减法，Q表示所有状态的集合，F 表示终止状态集合 W := {F, Q \ F }; // 此伪代码来源于维基百科，但维基百科此行有误 // Q \ F 也必须加入 W (WaitingSet) // 其它一些论文中将 W 初始化为 { min(F, Q \ F) }, 也不对 while (W is not empty) do choose and remove a set A from W for each c in ∑ do let X be the set of states for which a transition on c leads to a state in A for each set Y in P for which X ∩ Y is nonempty do replace Y in P by the two sets X ∩ Y and Y \ X if Y is in W replace Y in W by the same two sets else add min( X ∩ Y, Y \ X ) to W

缺点：空间消耗太大，仅适用于

Demo 非常小的 DFA 状态转移非常密集的 DFA
正则表达式的DFA一般比较小，也比较密， 用这种简单实现是可行的。Google RE2 中的 DFA 就是用了这种实现

实际应用中往往有包含数亿，甚至数十亿 状态的自动机，我们需要更紧凑的实现
紧凑的实现


库代码


示例代码


谢谢！


路径压缩一般可以将状态数压缩到原来的30% 甚至更少 路径压缩的DFA串匹配速度更快

在压缩的路径上是精确的串比较，无状态转移
路径压缩的适用范围

路径压缩可以应用到任意形状的DFA上


包括有环的 DFA Radix Tree 是一种应用了路径压缩的 Trie 在 MinDFA 上应用路径压缩可进一步减小状态数 无法（很难）进行修改操作 通用的DFA算法不再适用
最小化的 DAG 形状的 DFA (DAWG)
DFA 的最小化算法

Hopcroft 算法原理

Myhill–Nerode 等价

对任意输入，同一分区(子集)中两个状态 p, q的行为相 同，则 p, q 是 Myhill–Nerode 等价的 行为相同即：对任意w，δ(p,w) 与 δ(q,w)要么都是终止 状态，要么都不是终止状态 可直译为分区细化 Partition Refinement 是 Hopcroft 算法的一个关键操作， 该操作使用一个函数将集合的当前切分中的每个分区 进行再切分，直到不能继续切分

两个DFA同构

0~63 的二进制串
未最小化的 Tree 形状的 DFA (Trie)
最小化的 DAG 形状的 DFA (DAWG)
0~62 的二进制串
未最小化的 Tree 形状的 DFA (Trie)
最小化的 DAG 形状的 DFA (DAWG)
极端的例子：字符串 “1” ~ “99999”

标红中，扩展的全匹配

源代码

代码使用了 C++11

需要gcc-4.7以上版本 其他C++11编译器还没有测试过 /p/febird/source/brow se/trunk/febird/src/febird/automata /p/febird/source/brow se/trunk/febird/netbeans-cygwin/automata
Hopcroft 算法实现

逆自动机


双向链表（插入、删除均为 O(1) ）

一般DFA的逆是一个NFA，结构比较复杂 Trie的逆是一棵倒长的树，结构非常简单 用 smallmap 收集反向转移 用数组下标做链接 集合的一个切分可用一个置换(permutation)表达

切分是指将一个集合切分成多个互不相交的子集
工程实践

Double Array Trie & Bitmap Small CharSet DFA


启发式填充方法（往往可以填充到99.9%以上） Offline填充：BFS/DFS 遍历时填充，不需重定位 Online填充：无空位时需要重定位 min/max char + 指针（整数表示的相对偏移） 仅一个转移时，指针直接指向目标状态 有多个转移时，指针指向内存池中的Bitmap+数组 popcnt 的合理使用
相当于将 n个状态 压缩到 O(log(n)) 个状态 该自动机是 未规格化的
int int_t inБайду номын сангаасmax_t int8_t int16_t int32_t int64_t uint uint_t uintmax_t uint8_t uint16_t uint32_t uint64_t
未最小化的 Tree 形状的 DFA (Trie)
AC自动机可以用 Double Array 实现 AC自动机最坏情况时间复杂度是最优的
扩展的AC自动机

DFA 的实现

最简单的实现(需附带一个位图保存终止状态标志)
typedef unsigned int state_id_t; typedef unsigned char char_t; typedef state_id_t automata_t[][256];
有穷自动机的原理及应用
雷鹏 leipeng@ 2013-01-05
DFA 与 NFA

转移目标是一个状态集 合，可能包含多个状态
DFA 与 NFA 的转化

ADFA Acyclic DFA 无环自动机

一个无环自动机表达了一个有限的字符串集合 Trie

最简单，最大的 ADFA 又叫 DAWG (Directed Acyclic Word Graph) 需要的内存很小，极端情况下可将 n 压缩到O(log(n)) 随着字符串集合的增大，MinADFA 可能反而更小




汇合状态（Confluence State）：有多个前驱 状态的状态 需要克隆从汇合状态开始的路径 加入当前串之后，在当前串的路径上从后往 前执行最小化 每加入一个串，整个自动机是完全最小化的
ADFA 与字典序号

我们大多数情况下需要一个Map<string, Data>


可行的策略：


Waiting Set

可以任意次序进出 栈式的Waiting Set可使算法运行得更快
ADFA最小化的基本原理

ADFA最小化的实用算法

注册表

按右语言等价的定义，实现一个 map<TargetSet, StateID>

TargetSet 是 StateID 标识的状态的转移：pair(Char,Target) 的有序集合

Bitmap Byte Char Set DFA

在搜索项目中的应用

纠错词连接（类似最短分词+转录）

AC自动机 + BFS 最短路径

文本特征抽取（一遍扫描，使用AC自动机） 同义词表

相当于: map<word, SynonymSet>

Anchor 映射表

相当于: map<url, AnchorSet> 不同 url 的 AnchorSet 交集可能不空 这个功能使用了 NFA 的一种变形
普通的ADFA只能表示 Set<string>

附加一些数据，即可实现

从 ADFA 中得到一个串在该 ADFA中的字典序 将map<Key,Value> 的 Value保存一个数组中 最好也可以从字典序反推出ADFA中的一个串 每个状态同时保存该状态的右语言集合的尺寸 或者，每个状态转移(图的边)保存转移字符小于自己的转 移字符的其它目标状态的右语言尺寸之和
1.
2.
3.
4.
一旦执行最小化，前面的自动机状态不会 再变（深度优先，后序） 找出（当前串与上一个串的）公共前缀 CommonPrefix 从上一个串尾至CommonPrefixLen执行状 态合并（按注册表） 每次加入一个串，整个DFA是不完全最小 化的，完成时需要执行一次最终的最小化
ADFA的最小化：任意顺序的输入

MinADFA 最小化的无环自动机