`
liujiawinds
  • 浏览: 135797 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

NFA 和 DFA浅析

 
阅读更多

要深入了解正则表达式,必须首先理解有穷自动机。

有穷自动机(Finite Automate)是用来模拟实物系统的数学模型,它包括如下五个部分:

  • 有穷状态集States
  • 输入字符集Input symbols
  • 转移函数Transitions
  • 起始状态Start state
  • 接受状态Accepting state(s)

下图为一台有穷自动机


可以看到,该自动机包含四个状态q0, q1, q2, q3,两个输入字符a, b,转移函数如图所示,起始状态为q0,接受状态为q3。

有穷自动机,按照转移函数的不同,又可分为确定型有穷自动机(Determinism Finite Automate, DFA),与非确定型有穷自动机(Non-determinism Finite Automate, NFA)。
非确定有穷自动机容许转移函数不确定,换句话说,对任意状态,输入任意一个字符,可以转移到0个,1个或者多个状态。
下图是一台非确定有穷自动机,可以看到,对状态q0输入字符a,既可以转移到q0,也可以转移到q1,这就是“非确定”的意义所在。



对某个自动机来说,如果从起始状态,接受一系列输入字符,可以转移到接受状态,即认为这一系列字符可以被自动机接受。

如果两台自动机能够接受的输入字符串(或者叫做“正则语言”Regular Language)完全相同,则这两台自动机是等价的。
可以证明,对于每一个非确定有穷自动机,都存在与之等价的确定型有穷自动机(证明略)。

正则表达式就是建立在自动机的理论基础上的:用户写完正则表达式之后,正则引擎会按照这个表达式构建相应的自动机(可能是NFA,也可能是DFA,但它们必定是等价的),若输入一串文本之后,自动机抵达了接受状态,则这串文本可以“匹配”用户指定的正则表达式。

下面是同一个正则表达式 a|ab 对应的NFA和DFA
NFA


DFA





Mastering Regular Expression中,Friedl首先分析了NFA和DFA的区别,DFA比较快,但不提供Backtrack(回溯)功能,NFA比较慢,但提供了Backtrack功能。
在分析两种引擎的匹配过程时,Friedl指出,NFA是基于表达式的(Regex-Directed),而DFA是基于文本的(Text-Directed)。
举例来说,对于正则表达式 to(nite|knight|night),NFA在匹配最开始两个字符(to)之后,剩下的三个组件(component)是 nite, knight 和 night,于是正则引擎会依次尝试这三个选择分支(每次尝试一个);而DFA在匹配最开始两个字符之后,会将剩下的三个选择拆分作字符,并行尝试,也就是说,匹配 to 之后,先匹配 k 或者 n ,如果 k 不能匹配,则放弃 knigth 所在的分支,再匹配 i ,再匹配 t 或 g ……这样继续下去,直到匹配结束。

不幸的是,Friedl对匹配过程的分析,是完全错误的——引擎的不同,是指构建的自动机的不同,而不是匹配算法的不同!
DFA引擎在任意时刻必定处于某个确定的状态,而NFA引擎可能处于一组状态之中的任何一个,所以,NFA引擎必须记录所有的可能路径(trace multiple possible routes through the NFA),NFA之所以能够提供Backtrack的功能,原因就在这里。
传统的NFA匹配算法是带回溯的深度优先搜索(backtracking depth-first search,就是上文所说的Regex-Based过程),而新的PCRE算法提供了效率更高的广度优先搜索,可以同时保持所有可能的NFA状态(请参考http://www.cl.cam.ac.uk/Teaching/current/RLFA/,尤其是Lecture Notes的section 2.2)。

Friedl的错误就在这里,他混淆了应用PCRE算法的NFA与DFA的匹配过程。
需 要指出的是,即使应用PCRE算法,NFA的速度仍然低于DFA,这是由NFA需要同时保存多种可能的性质决定的。从理论上说,如果我们不需要应用 Backtrack,完全可以从NFA构造出等价的DFA,再进行匹配,这样能大大提高速度——代价是,DFA需要更多的空间。

原文地址:http://www.cnblogs.com/u2usoft/archive/2006/06/06/419003.html

分享到:
评论

相关推荐

    NFA到DFA的转化程序

    在编译原理中,NFA(非确定有限状态自动机)和DFA(确定有限状态自动机)是两种重要的计算模型,广泛应用于正则表达式和形式语言的处理。本主题将深入探讨如何将NFA转换为DFA,并通过一个Java实现的程序来展示这一...

    编译原理NFA转DFA实现(python).zip

    在编译原理中,非确定有限自动机(Non-Deterministic Finite Automaton,简称NFA)和确定有限自动机(Deterministic Finite Automaton,简称DFA)是两种重要的概念。NFA转DFA是编译器设计的一个关键步骤,它有助于...

    编译原理Java实现NFA到DFA的等价变换

    FINITE AUTOMATON(FA)是自动机理论的基本概念,分为两种:Deterministic Finite Automaton(DFA)和Non-Deterministic Finite Automaton(NFA)。本文将介绍使用Java语言实现NFA到DFA的等价变换。 第一部分:NFA...

    NFA到DFA的转换(C语言实现)

    其中,非确定性有限状态自动机(Non-Deterministic Finite Automaton,NFA)和确定性有限状态自动机(Deterministic Finite Automaton,DFA)是两种常见的模型。本项目通过C语言实现了NFA到DFA的转换,这是一项在...

    NFA到DFA.rar_NFA DFA_NFA到DFA转换_nfa and dfa pdf_nfa-dfa_nfa,dfa

    在计算机科学领域,正则表达式和自动机理论是编译原理的重要组成部分,其中NFA(非确定性有限状态自动机)和DFA(确定性有限状态自动机)是两种核心概念。NFA到DFA的转换是一个重要的理论与实践问题,尤其是在编译器...

    NFA到DFA的转换

    2. **NFA到DFA的转换**:使用子集构造法将NFA转换为DFA,这可能涉及到复杂的数据结构如集合和状态映射。 3. **输出DFA**:程序会输出转换后的DFA,包括其状态、转移函数和终止状态。 4. **DFA最小化**:如果提供此...

    NFA到DFA转换

    NFA到DFA转换 存储NFA与DFA,编程实现子集构造法将NFA转换成DFA。 (1)确定NFA与DFA的存储格式,为3个以上测试NFA准备好存储文件。 (2)用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。 (3)经测试无误。...

    NFA转DFA程序代码

    本人用c++写的一个将NFA转换成DFA的程序,希望大家指教。

    从nfa到dfa代码

    首先,我们需要理解NFA和DFA的基本概念。NFA是一种允许在某个状态下同时转移到多个状态的自动机,而DFA则是每个状态下只能转移到一个特定状态的自动机。尽管NFA更灵活,但DFA在执行效率和实现上更具优势,因为它们...

    自动机nfa->dfa邻接表实现

    自动机主要有两种类型:非确定性有限自动机(NFA)和确定性有限自动机(DFA)。本作业主要探讨如何将NFA转换为DFA,并通过数据结构——邻接表来实现这一过程。 非确定性有限自动机(NFA)是一种允许存在多种转移...

    NFA转DFA&DFA最小化&NFA与DFA语言子集NFA转DFA&DFA最小化&NFA与DFA语言子集

    在计算机科学领域,尤其是理论计算机科学和形式语言理论中,NFA(非确定性有限状态自动机)和DFA(确定性有限状态自动机)是两种重要的模型,用于描述正则语言。本代码集合着重于NFA转换为DFA的过程以及DFA的最小化...

    编译原理课程设计NFA和DFA

    在编译原理中,NFA(非确定有限自动机)和DFA(确定有限自动机)是两种重要的概念,它们在形式语言理论和编译器设计中占据着核心地位。这两种自动机主要用于识别和处理正规集,即一组字符串,它们在计算机科学中广泛...

    nfa-dfa.rar_DFA_Dfa Nfa_NFA DFA_NFA DFA c++_nfa

    在计算机科学领域,自动机理论是研究计算过程的重要分支,其中非确定性有限状态自动机(NFA)和确定性有限状态自动机(DFA)是两种基本的模型。本文将深入探讨NFA和DFA的概念、性质,并介绍它们之间的转换,最后将...

    编译原理课程设计(NFA转DFA)

    通过这次课程设计,学生不仅能深入理解NFA和DFA的理论,还能通过实践掌握NFA转DFA的算法,这对今后在编译器设计和相关领域的工作大有裨益。同时,这一过程也展示了理论知识与编程实践相结合的重要性,强化了问题解决...

    正规式转NFA转DFA转MFA

    综上所述,"正规式转NFA转DFA转MFA"项目是关于形式语言理论的Python实现,它涵盖了正规式与有限自动机之间的转换,并提供了图形化的表示方式,便于理解和调试。通过学习和理解这个项目,可以深入理解这些抽象概念,...

    c++实现NFA与DFA转换

    采用c++语言编程,从而实现NFA与DFA之间的转换,代码简单

    nfa-dfa.rar_Dfa Nfa_NFA DFA_nfa转dfa代码_有助于学写编译原理的基本思路_编译原理中nfa转df

    本资源包“nfa-dfa.rar”主要关注两种类型的状态自动机:非确定有限状态自动机(Non-Deterministic Finite Automaton, NFA)和确定有限状态自动机(Deterministic Finite Automaton, DFA),以及如何将NFA转换为DFA...

    编译原理正则表达式转NFA转DFA DFA最小化 Cpp代码

    编译原理课的大作业 包含三个小实验 在一个cpp文件里 正则表达式转换为nfa nfa转换为dfa dfa最小化 个人原创代码

    NFA转换为DFA(子集构造法)

    在计算机科学领域,正则表达式和自动机理论是重要的组成部分,其中非确定性有限状态自动机(NFA,Non-Deterministic Finite Automaton)和确定性有限状态自动机(DFA,Deterministic Finite Automaton)是两种常用的...

    正则表达式转换为NFA,dfa,确定化

    正则表达式可以通过一系列转换步骤转化为非确定有限自动机(NFA)和确定有限自动机(DFA),这两种都是形式语言理论中的关键概念。 首先,让我们详细了解正则表达式。它由一些基本字符和操作符组成,如点号(.)...

Global site tag (gtag.js) - Google Analytics