- 综合排序
- 最热优先
- 最新优先
- 来自专栏Java架构师必看
DFA和NFA
2.DFA和NFA 引用 理解DFA和NFA 正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。 DFA与NFA机制上的不同带来5个影响： 1. 模块、Java和.NET的regex库，都是NFA的。 NFA缺省采用greedy量词（见item 4）； 5. NFA可能会陷入递归调用的陷阱而表现得性能极差。 我这里举一个例子来说明第3个影响。 由此可知，要让NFA正确工作，应该使用 /perlman|perl/ 模式。 通过以上例子，可以理解为什么NFA是最左子式匹配，而DFA是最长左子式匹配。
1.1K20发布于 2021-07-13 - 来自专栏姓王者的博客
编译原理:NFA转DFA
非确定有限自动机(Non-Deterministic Finite Automaton,NFA)也是一种计算模型,与 DFA 相比,它在状态转移上具有不确定性。 工作原理 NFA 在处理输入字符串时,对于每个输入符号,它可以同时尝试多个可能的状态转移。 如果存在一条从初始状态到某个接受状态的路径,使得沿着该路径处理完整个输入字符串,则认为该字符串被 NFA 接受。 示例 考虑一个 NFA 用于识别包含 01 子串的二进制字符串,其状态转移图如下： +---0---+ | | v | q0 --0,1--> q0 --0--> ： 通过以上步骤,我们成功地将 NFA 转换为了 DFA。
63110编辑于 2025-03-26 - 来自专栏图灵技术域
速读-NFA的GPU加速器
Specifically, the authors identify two performance bottlenecks in the NFA matching process, one is the Moreover, to the best of my knowledge, in the context of NFA processing, no prior work has considered From a high perspective, I think the proposed new data structure to store NFA pattern in this paper is “iNFAnt: NFA pattern matching on GPGPU devices.” “GPU-based NFA implementation for memory efficient high speed regular expression matching.”
2.6K40发布于 2021-05-21 - 来自专栏iOS底层原理
编译器原理-who|what|where的NFA构造
一·NFA构造 A2D117CF9487C0AD47FC11A9C17548F7.png 第一步写出who where what 的NFA 画出状态图，添加空步骤ε 使用ε-closure 算法写出所有可能的状态 步骤一，初始化阶段q0 DNF NFA 字符集：whatore 步骤二，链路w经过 步骤ε有h 的NFA 集合为S2 步骤三，链路h经过步骤ε 分别有S4 S5 S6 集合NFA 步骤四，链路o a
70230发布于 2021-03-17 - 来自专栏Coding迪斯尼
自己动手写编译器:从NFA到DFA
上一节我们完成了使用NFA来识别字符串的功能。NFA有个问题就是其状态节点太多，使用起来效率不够好。本节我们介绍一种叫“子集构造”的算法，将拥有多个节点的NFA转化为DFA。 在上面代码中我们定义了DFA节点，由于一个DFA节点由一组NFA节点转换而来，因此在它的定义中有一个NFA节点的指针数组。 (n NfaDfaConverter) MakeDTran(start NFA) { //根据输入的nfa状态机起始节点构造dfa状态机的跳转表 startStates := make([]NFA, 上面代码的算法核心在函数MakeDTran,它执行了我们上面提到的算法，首先获得NFA状态机的起始节点，然后通过epsilon闭包操作获得一组NFA节点，用这组节点创建一个对应的DFA节点。 is nfa are: {10,9,12,13,} DFA state : 6, it is nfa are: {16,28,24,23,26,28,} DFA state : 7, it is nfa
1K20编辑于 2023-02-26 - 来自专栏机器学习炼丹之旅
编译原理：第三章 词法分析
NFA和DFA的不同在于: δ的值域是S的子集，δ：S×Σ^* →2^S 开始状态有不止一个 接受ε作为输入符号 3.2.2 NFA的确定化 若规定NFA的初态集中只有唯一一个元素，即NFA的初态唯一 ，且状态转换函数单值，则该NFA即为DFA。 DFA是NFA的特例： 对每一个NFA N一定存在一个DFA M，使得L(M)=L(N)即对每个NFA N存在着与之等价的DFA M。 注意：与某一NFA等价的DFA不唯一。 3.3.3 NFA确定为DFA的原因 使用NFA判定某个输入符号串的时候，可能出现不确定的情况：不知道下面选择哪个状态。如果选择不好，该输入符号串可能不能到达终止状态。 此外,用来描述语言的正规式更容易构造出识别同一语言的NFA。 3.3.4 NFA的确定化：子集法 基本思想： 让DFA的每一个状态对应NFA的一组状态。
5.2K11编辑于 2022-08-09 - 来自专栏前端架构
深入正则表达式(3):正则表达式工作引擎流程分析与原理释义
总的来说， DFA可以称为文本主导的正则引擎 NFA可以称为表达式主导的正则引擎 NFA与DFA工作的区别： 我们常常说用正则去匹配文本，这是NFA的思路，DFA本质上其实是用文本去匹配正则。 所以，在表达能力上，NFA引擎秒杀DFA引擎。 但是NFA以表达式为主导，因而NFA更容易操纵，因此一般程序员更偏爱NFA引擎！ 当今市面上大多数正则引擎都是NFA引擎，应该就是胜在表达能力上。 因为NFA引擎比较灵活，很多语言在实现上有细微的差别。所以后来大家弄了一个标准，符合这个标准的正则引擎就叫做POSIX NFA引擎，其余的就只能叫做传统型NFA引擎咯。 POSIX NFA引擎 POSIX NFA引擎主要指符合POSIX标准的NFA引擎，与传统的 NFA 引擎类似，不同的一点在于：提供longest-leftmost匹配，也就是在找到最左侧最长匹配之前， 因此，POSIX NFA 引擎的速度慢于传统的 NFA 引擎；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索。
2.5K00发布于 2020-06-06 - 来自专栏Gnep's_Technology_Blog
雷达检测及MATLAB仿真
=e+2','pd=.8, nfa=e+6','pd=.95, nfa=e+10','pd=.999, nfa=e+13'); grid 2）仿真 改善因子相对于非相干积累脉冲数的关系曲线 =e+12','pd=.8, nfa=e+12','pd=.95, nfa=e+12','pd=.99, nfa=e+12'); grid 2）仿真 积累损失相对于非相干积累脉冲数的关系曲线 = input1; pfa = np * log(2) / nfa; else pfa = input1; nfa = np * log(2) / pfa; end sqrtpfa , 1, snr); prob10(index) = pd_swerling1 (nfa, 10, snr); prob50(index) = pd_swerling1 (nfa, 50 , 1, snr); prob10(index) = pd_swerling2 (nfa, 10, snr); prob50(index) = pd_swerling2 (nfa, 50
86990编辑于 2023-11-11 - 来自专栏XINDOO的专栏
从0到1打造正则表达式执行引擎(二)
DFA和NFA 我们已经多次提到了NFA和DFA，它俩究竟是啥？有啥区别？ 首先，NFA和DFA都是有限状态机，都是有向图，用来描述状态和状态之间的关系。 还有，上图有 总结下NFA和DFA的区别就是，有ε边或者某个节点对同一输入对应多个状态的一定是NFA。 DFA和NFA存在等价性，也就是说任何NFA都可以转化为等价的DFA。 NFA转DFA 算法 NFA转DFA的算法叫做子集构造法，其具体流程如下。 步骤1: NFA的初始节点和初始节点所有ε可达的节点共同构成DFA的初始节点，然后对初始DFA节点执行步骤2。 然后对DFA的节点0执行步骤1，找到NFA中所有a可达的NFA节点(1#2#4#6#8#9)构成NFA中的节点1，如下图。 ? 可以看出DFA图节点明显少于NFA，但NFA更容易看出其对应的正则表达式。
78820发布于 2021-01-22 - 来自专栏Coding迪斯尼
自己动手写编译器：使用NFA状态机识别字符串
在前面章节中我们构建了NFA状态机，现在我们看看如何使用它来识别给定字符串是否合法。首先我们先构造如下正则表达式对应的NFA,在input文件的表达式部分输入： ({D}.{D} | {D}. {D}) 这个表达式的目的是识别浮点数，用我们前面做好的代码生成的NFA状态机如下： 这里我们需要引入两个个概念及其对应操作，首先是epsilon-clousure操作， 它表示给定一系列初始状态后 我们看看上面算法的代码实现，增加一个名为nfa_interpretation.go的文件，输入代码如下： package nfa import ( "fmt" "math" ) type , c int) []*NFA { result := make([]*NFA, 0) for _, elem := range input { if int(elem.edge NFA, 0) startStates = append(startStates, state) statesCopied := make([]*NFA, len(startStates
96121编辑于 2022-12-02 - 来自专栏韩曙亮的移动开发专栏
【计算理论】非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA )
一、非确定性有限自动机 组成部分 非确定性有限自动机 : Nondeterministic Finite Automaton , NFA ; Q① 状态集 : 有限个状态 ; ② 字母表 : 接受状态集 : 是 可接受状态 , 是 的子集 , 记做 , 与 可接受状态相对的是不可接受状态 ; 二、确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 等价 确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 之间是相互等价的 ; 确定性的有限自动机 ( DFA ) 可以 看作是非确定性有限自动机 ( NFA ) ; 确定性有限自动机 1 11 个后继状态 ; 确定性有限自动机 ( DFA ) 就是 特殊的 非确定性有限自动机 ( NFA ) ; 可以证明非确定性有限自动机 ( NFA ) , 必定有一个 确定性有限自动机 ( DFA 消除不确定性 : 下面的表格就是将 非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA ) 的结果 , 将状态集合当做一个新的状态 , 新状态由之前的 NFA 中的不同状态组合而来
5.5K00编辑于 2023-03-28 - 来自专栏布鲁斯鱼的妙想天开
ReDoS：正则也许会让你的系统更脆弱
引 Evil Regex 大敌当前 知己知彼，百战不殆 NFA vs DFA Thompson NFA 构造 vs DFA 为什么主流编程语言这么慢？ 这种计算模型比较常见，所以我们就着重关注 NFA 和 DFA 的对比。 理论上，每一条正则表达式都可以等同转换成一个 NFA 状态机，那么如果使用 NFA 进行匹配，如何处理猜测分支就很重要了。下面我们来看一个简单遍历猜测的例子。 Thompson NFA 构造 vs DFA 为什么使用了 Thompson NFA 构造出的正则匹配会快这么多呢？主要的原因是：通过划分多个子表达式，合并相同的内容，从而减少了回溯次数。 NFA 图片 为什么主流编程语言这么慢？
1.6K40编辑于 2022-11-02 - 来自专栏XINDOO的专栏
[翻译]正则引擎的几种分类
正则引擎有两个大分类，DFA和NFA，像Perl、Java、.Net、PHP、Python、Ruby……等大多是工具都是用了NFA引擎。 少数广泛被使用的工具如mawk使用了POSIX NFA引擎（NFA的一种变种）。以高效著称的工具采用了更为高效的DFA引擎。 传统的NFA引擎 NFA引擎中使用的非确定有限状态机(Nondeterministic finite automation)是一种由要匹配的表达式驱动的算法。 POSIX NFA 引擎 POSIX NFA引擎类似于传统NFA引擎，但是当找到成功的匹配项时，它将会记录匹配结果，并且尝试其他可用的替代方法以查找是否可以找到更长的最左边的匹配。 由于DFA引擎速度快，但NFA引擎的功能多，因此，混合NFA / DFA引擎试图将二者的优势结合起来。
33510编辑于 2024-08-07 - 来自专栏Coding迪斯尼
自己动手写编译器:从正则表达式到NFA状态机
%% 我们将读取上面内容并根据给定的正则表达式创建NFA状态机。 , end *NFA) (newStar *NFA, newEnd *NFA) { /* expr -> expr or expr | cat_expr 一个正则表达式可以分解成两个表达式的并 , end *NFA) (newStart *NFA, newEnd *NFA) { /* cat_expr -> cat_expr | factor */ e2Start , end *NFA) (newStart *NFA, newEnd *NFA) { /* factor -> term* | term+ | term? , end *NFA) (newStart *NFA, newEnd *NFA) { /* term -> [...] | [^...] | [] | [^] | . | (expr
1.7K20编辑于 2022-12-02 - 来自专栏韩曙亮的移动开发专栏
【计算理论】计算理论总结 ( 非确定性有限自动机 NFA 转为确定性有限自动机 DFA | 示例 ) ★★
文章目录 一、NFA 转 DFA 示例 1 二、NFA 转 DFA 示例 2 三、NFA 转 DFA 示例 3 一、NFA 转 DFA 示例 1 ---- 将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ; NFA 的状态集 \rm \{ 1,2,3 \} , 字符集 \rm \{ a,b \} ; 从 起始状态 1 开始分析 , 读取 \rm \varepsilon 无条件跳转到 } , 写到下面表格中 ; \rm \{1, 3\} 状态 下读取 \rm a 字符结果是 \rm \{1, 3\} , 读取 \rm b 字符结果是 \{2\} , 上述分别是 NFA ) 转换成 确定性有限自动机 ( DFA ) 二、NFA 转 DFA 示例 2 ---- 将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ; NFA 的状态集 \rm \{ 1,2,3 转 DFA 示例 3 ---- 将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ; NFA 的状态集 \rm \{ 1,2 \} , 字符集 \rm \{ a,b \}
85300编辑于 2023-03-28 - 来自专栏iOS底层原理
编译器原理-Review我几个月前写的笔记
·····} 二·有限状态集 输入的字符串---->FA------>{1,0} M = {∑，S，q0，F，σ} ∑ 字母表 S 状态集 q0 初始状态 F 终结状态集 σ转移函数 三· RE->NFA 49DEB1701DBD5223AFADCAFC89D6F9BB.png 注释的正则表达式 QQ截图20210317145754.png ε-closure eplison闭包算法生成DFA 对于上面的NFA ，计算机需要一个确定的状态 所以需要把NFA转化为DFA，而且DFA是NFA的子集 反正就是NFA比DFA大因为有很多确定表达和不确定表达 72FFC5275E9B7E15E01CD319C137E6E8
63030发布于 2021-03-17 - 来自专栏AI科技大本营的专栏
关于正则表达式，这篇都讲清楚了
) 非确定型有穷自动机 ps：当然还有一种引擎为：POSIX NFA，这是根据NFA引擎出的规范版本，但因为使用较少所以我们这里也就不重点讲解。 NFA引擎执行原理： 猪哥同样画了一个简易的NFA引擎执行过程图方便大家理解 ? 关于这两种引擎的总结，猪哥引用《精通正则表达式》书本中的一句话来概括： DFA（电动机） 和NFA（汽油机） 都有很长的历史，不过，正如汽油机一样，NFA 的历史更长一些。 上面我们了解到，绝大多数的编程语言都采用的是NFA引擎，而NFA引擎的特点是：功能强大、但有回溯机制所以效率慢。 所以我们需要学习一些NFA引擎的一些优化技巧，以减少引擎回溯次数以及更直接的匹配到结果！ 针对NFA引擎的可优化的点其实挺多的，为了方便大家记忆，猪哥也画幅结构图归纳一下，方便大家收藏细看。 ?
1.6K30发布于 2020-02-26 - 来自专栏luoheng
正则表达式 引擎分类
DFAawk, egrep, flex, lex, MySQL传统型NFAJava, grep, less, more, Perl, PythonPOSIX NFAmawk, GNU EmacsDFA/NFA , {m, n}）是匹配优先的区别引擎原理NFA是表达式主导，目标文本的某个字符可能被正则表达式中的不同部分重复检测。 NFA的编译会快一些，内存使用较少。匹配速度传统NFA在匹配失败前，必须尝试正则表达式所有变体。POSIX NFA必须总是尝试所有正则表达式变体，以找到最长的匹配文本。 匹配结果DFA和POSIX NFA返回最左最长的匹配文本，传统NFA可能返回其他结果。 匹配能力NFA提供一些DFA不支持的功能：捕获括号内的子表达式文本，并支持反向引用环视忽略优先两次，以及有序的多选结构（DFA总是返回最左最长匹配）占有优先量词固化分组
54200编辑于 2022-08-28 - 来自专栏Gnep's_Technology_Blog
雷达检测及MATLAB仿真
=e+2','pd=.8, nfa=e+6','pd=.95, nfa=e+10','pd=.999, nfa=e+13'); grid 2）仿真 改善因子相对于非相干积累脉冲数的关系曲线 =e+12','pd=.8, nfa=e+12','pd=.95, nfa=e+12','pd=.99, nfa=e+12'); grid 2）仿真 积累损失相对于非相干积累脉冲数的关系曲线 = input1; pfa = np * log(2) / nfa; else pfa = input1; nfa = np * log(2) / pfa; end sqrtpfa , 1, snr); prob10(index) = pd_swerling1 (nfa, 10, snr); prob50(index) = pd_swerling1 (nfa, 50 , 1, snr); prob10(index) = pd_swerling2 (nfa, 10, snr); prob50(index) = pd_swerling2 (nfa, 50
1.2K91编辑于 2023-11-11 - 来自专栏韩曙亮的移动开发专栏
【计算理论】计算理论总结 ( 正则表达式转为非确定性有限自动机 NFA | 示例 ) ★★
文章目录 一、正则表达式转为非确定性有限自动机 NFA 要点 二、正则表达式转为非确定性有限自动机 NFA 示例 1 三、正则表达式转为非确定性有限自动机 NFA 示例 2 四、正则表达式转为非确定性有限自动机 NFA 示例 3 一、正则表达式转为非确定性有限自动机 NFA 要点 ---- 正则表达式转为非确定性有限自动机 NFA 流程 : ① 原子自动机 : 首先要构造 原子自动机 , 从 非接受状态 指向 , 使用 \varepsilon 箭头从 接受状态 指向 开始状态 ; 注意所有的接受状态 , 都要使用 \varepsilon 箭头指向开始状态 ; 二、正则表达式转为非确定性有限自动机 NFA 示例 1 ---- 将正则表达式 \rm (0 \cup 1)^*000 ( 0 \cup 1 )^* 转为 NFA ; 构造原子自动机 : 注意从 非接受状态 \to 接受状态 ; \rm 示例 2 ---- 将正则表达式 \rm ( ( (00) ^* (11) ) \cup 01 )^* 转为 NFA ; 构造原子自动机 : 注意从 非接受状态 \to 接受状态 ; 00
80100编辑于 2023-03-28
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号