2.DFA和NFA 引用 理解DFA和NFA 正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。...DFA与NFA机制上的不同带来5个影响： 1....只有NFA才支持lazy和backreference等特性； 3. NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。...由此可知，要让NFA正确工作，应该使用 /perlman|perl/ 模式。 通过以上例子，可以理解为什么NFA是最左子式匹配，而DFA是最长左子式匹配。...实际上，如果仔细分析，关于NFA和DFA的不同之处，都可以找出道理。而明白这些道理，对于有效应用正则表达式是非常有意义的。
上一节我们完成了使用NFA来识别字符串的功能。NFA有个问题就是其状态节点太多，使用起来效率不够好。本节我们介绍一种叫“子集构造”的算法，将拥有多个节点的NFA转化为DFA。...在上一节我们描述的epsilon闭包操作可以看到，实际上所有由epsilon边连接在一起的节点其实都能看作是一个状态节点，由此我们就能通过epsilon操作将多个节点转化为一个DFA节点，同时epsilon...状态机中，它最多包含254个节点，同时状态机只接收来自ascii表中数值从0到128的字符，这次我们构造的DFA状态机将不像上次构造的NFA状态机那样使用链表结构，这次我们使用跳转表结构，我们将构造一个二维数组...接下来我们设计用于将NFA转换成DFA的类，其代码为： go type NfaDfaConverter struct { nstates int //当前dfa 节点计数...每新建一个DFA节点时，它的mark标志位会设置成false,这表明我们还没有为它设置跳转边，函数getUnMarked用于将当前所有mark设置为false的DFA节点中找出创建时间最早的那个。
将tensor转换为numpy import tensor import numpy as np def tensor2img(tensor, out_type=np.uint8, min_max=...如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章目录 一、NFA 转 DFA 示例 1 二、NFA 转 DFA 示例 2 三、NFA 转 DFA 示例 3 一、NFA 转 DFA 示例 1 ---- 将下图的 非确定性有限自动机 NFA 转为确定性有限自动机...\{3\} , 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ; \{2,3\} 状态下读取读取 \rm a 字符结果是 \{1, 2,3...\} , 读取 \rm b 字符结果是 \{3\} , 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ; \{3\} 状态下读取读取...如下 : 详细推理过程 : 【计算理论】非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA ) 二、NFA 转 DFA 示例 2 ---- 将下图的 非确定性有限自动机 NFA...如下 : 三、NFA 转 DFA 示例 3 ---- 将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ; NFA 的状态集 \rm \{ 1,2 \} , 字符集 \rm
, 将这两个状态组成的集合看做一个新的状态 , 图片 四、NFA 转 DFA ( 1 ) 开始状态 读取 a 字符 后继状态分析 图片 表格 第 2 行 第 2 列 : 1 ....不再考虑 , 开始分析 { 2 } 状态 ; 图片 七、NFA 转 DFA ( 4 ) 2 22 状态读取 a 字符后续状态分析 图片 表格 第 3 行 第 2 列 : 1 ....转 DFA ( 9 ) 选取后续需要分析的状态 选取原则 : 没有出现过的状态 , 都要进行分析 ; { 1 , 2 , 3 } 是 新出现的状态 , 因此将这两个状态加入表格中 , 进行分析 ; 加入该状态后...转 DFA ( 14 ) 结果分析 1 ....消除不确定性 : 下面的表格就是将 非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA ) 的结果 , 将状态集合当做一个新的状态 , 新状态由之前的 NFA 中的不同状态组合而来
还有，上图有 总结下NFA和DFA的区别就是，有ε边或者某个节点对同一输入对应多个状态的一定是NFA。 DFA和NFA存在等价性，也就是说任何NFA都可以转化为等价的DFA。...这也是为什么我们要将引擎中的NFA转化为DFA的主要原因。 NFA转DFA 算法 NFA转DFA的算法叫做子集构造法，其具体流程如下。...步骤2: 对当前DFA节点，找到其中所有NFA节点对输入符号X所有可达的NFA节点，这些节点沟通构成的DFA节点作为当前DFA节点对输入X可达的DFA节点。...efinishedState.add(eState); } } // 将NFA...参考资料 nfa转dfa
但是在表达形式上, NFA 将这种二义性(或者说多种可能性)表现在转换上了; 而与之不同, DFA 将二义性表达在状态里, 多种可能性被聚合在状态里, 消除了转换的二义性....如果不是计算机处理,而是人脑,其实潜意识里就已经存在那个 “NFA 转 DFA”的过程, 人脑可以“并发地”同时走多条路径....这么看,DFA 转 NFA 其实是把人类的潜意识里存在的处理方式“教”给了计算机. 范围输入带来的二义性 工程实践与教科书的区别在于, 教科书总是假设一个理想环境, 而工程并非如此....前文中讲 NFA 转 DFA 时, 其实忽略一个现实: "转换可以是针对一个范围的输入" ....针对这种情况, 在将 NFA 转换 DFA 时, 需要设计一个算法, 消除 NFA 的存在交集的转换的二义性, 算法过程如下: 上例中, 起点处存在如下 4 个转换: 我们把每个转换的输入区间看作一个集合
含义: 在当前状态为s_i，输入符号为 a 时，将转换为下一状态s_j，我们把s_j称为s_i的一个后继状态。 (4) s_0 ∈S，是唯一的一个初态。...DFA是NFA的特例： 对每一个NFA N一定存在一个DFA M，使得L(M)=L(N)即对每个NFA N存在着与之等价的DFA M。 注意：与某一NFA等价的DFA不唯一。...但是，我们不能说该输入符号串不能被该NFA接受。如果通过尝试的方法，不断试探来确定输入符号串是否可被接受，那么判定的效率将降低。解决的方法是将NFA转换为等价的DFA。...3.3.2 化简步骤 步骤1： 将DFA的状态集分为互不相交的子集使得任何不同的两子集中的状态都是可区别的，而每个子集中的任何两个状态是等价的。...2.然后分解弧上正规式，用替代规则引入新状态结点，所有的新结点取不同的名字但同一结点的不同射出弧可以同名 3.直到所构造的FA中每条弧上都标记为单输入符号为止 4.用子集法将NFA确定化，用划分法将DFA
正则引擎主要可以分为基本不同的两大类：一种是DFA（确定型有穷自动机），另一种是NFA（不确定型有穷自动机）。简单来讲，NFA 对应的是正则表达式主导的匹配，而 DFA 对应的是文本主导的匹配。...可以看到，DFA匹配过程中文本中的字符每一个只比较了一次，没有吐出的操作，应该是快于NFA的。...另外，不管正则表达式怎么写，对于DFA而言，文本的匹配过程是一致的，都是对文本的字符依次从左到右进行匹配，所以，DFA在匹配过程中是跟正则表达式无关的，而 NFA 对于不同但效果相同的正则表达式，匹配过程是完全不同的...在上例中，如果将正则换为 ab{1,3}?c 则匹配过程变成了下面这样（橙色为匹配，黄色为不匹配）， ? 由此可见，在非贪婪模式下，第2步正则中的b{1,3}?...转自：不死码农
) = AB|AC (A|B)C = AC|BC A(伊姆逊)|(伊姆逊)A = A A* = AA*|(伊姆逊)=A|A* = (A|(伊姆逊))* (A*)* = A* 正规文法到正规式的转换： 将正规文法中的每个非终结符表示成关于它的一个正规式方程...正规式与有穷自动机： 利用有穷自动机构造词法分析程序的方法是： 从语言单词的描述中构造出非确定的有穷自动机； 再将非确定的有穷自动机转化成确定的有穷自动机； 将其化简为状态最少化的DFA； 对DFA的每个状态构造一小段程序将其转化为识别语言单词的词法分析程序...； 确定有穷自动机（DFA）： 非确定有穷自动机（NFA）： ?...由正规式R构造NFA： ? NFA确定化为DFA的方法： ? DFA的化简： ? 有穷自动机到正规式的转换，参考正规式转换为有穷自动机，基本的就是那三个规则转换；
java-将Map 转换为Map 如何将Map转换为Map？...String) entry.getValue()替换为entry.getValue().toString()。...:) 尝试将狭窄的泛型类型转换为更广泛的泛型类型意味着您一开始使用的是错误的类型。 打个比方：假设您有一个程序可以进行大量的文本处理。 假设您使用Objects(!!)...valueTransformer) 在哪里 MapUtils.transformedMap(java.util.Map map, keyTransformer, valueTransformer) 仅将新条目转换为您的地图...转换为Map的方法。
---- 2.4.1 将正则表达式转换为 NFA ---- 非确定的自动机是一个很有用的概念，因为它很容易将一个（静态的、说明性的）正则表达式转换成一个（可模拟的、准可执行的）NFA。...转换算法可以将任何一个正则表达式转换为有一个尾巴和一个脑袋的 NFA，它的尾巴即开始边，简称为尾；脑袋即末端状态，简称为头。...类似地，NFA 或者是基本元素，或者是由多个较小的NFA组合而成。 将正则表达式转换至 NFA ，我们利用单词 IF、ID、NUM 以及 error 的一些表达式来举例说明这种转换算法。...由此得到的结果（在合并了某些等价的 NFA 状态之后）如下图所示： ---- 2.4.2 将 NFA 转换为 DFA ---- 用计算机程序实现确定的有限自动机（DFA）较容易。...由 NFA 构造一个 DFA，使得 NFA 的每一个状态集合都对应于 DFA 的一个状态。因为 NFA 的状态个数有限 （n 个），所以 DFA 的状态个数也是有限的（至多为 2^n个）。
有限状态机是不满足正则表达式引擎的要求的，因为正则表达式对应有分支，状态可能会存在多个等情况，所以延伸出了以下两种引擎 DFA DFA是确定性有限自动机，它会先扫描表达式，将表达式编译成内部形式，然后在读入字符后状态可以到达多个...但因为DFA只含有有限多个状态，所以不支持反向引用，不可以捕获表达式，但相对NFA来说，DFA的速度是稳定的，对于一些简单场景来说是足够了。...举例说明：对于正则表达式ac|ad|adc|ea,我们假设匹配adc,首先读入字符a, DFA记录后续可能的状态ac,ab,adc,ea不符合直接抛弃，读入字符d, 状态变换为ad,adc, 此时ad已经到达最终态...NFA NFA不会像DFA记录所有的状态，它只会记录中间状态。...其实与其将NFA看作有穷自动机，不如将NFA看作一棵树，NFA使用深度优先遍历的方式来向下匹配，匹配到叶子节点就完成一次匹配，匹配不成功就回溯到上一个节点，继续对未访问过的子节点进行匹配。
Lexical Analysis(词法分析阶段) 任务：将字符串分解成为[Type, (Value)]元组的形式的词法单元。...由于DFA的状态转移路径是唯一的，所以作为状态查询图时，无论成功或者失败只需要运行一次，但NFA就可能需要运行多次。...正则表达式是可以转换为NFA形式的，或许你已经在一些可视化正则表达式的网站上[https://regexper.com ]见过类似的形式。...如果一个DFA和一个NFA能够识别的字符集是一致的，则称它们为等价的，对于任意NFA，一定存在一个DFA与其等价，由NFA构建DFA的过程被称为DFA的确定化，也就是NFA——>DFA的过程。...状态集合 ，使用矩阵记录每个ε -closure集合转换前后的集合，最后对整个状态转移矩阵进行标记重命名，就可以得到一个DFA，事实上转化后的DFA中的每一个状态，就是NFA中的一个ε -closure
)，在每个状态，它都能根据当前输入确定下一个状态，但很多情况下，我们很难直接从正则表达式去构造DFA，因此我们需要将其扩展一下变成NFA(no-deterministic finite automa)。...相比于前者，NFA多了一种边叫ε,从一个状态节点可以发出多条这样的边,这种边表示不用输入任何字符就可以抵达给定状态，例如正则表达式any|d NFA比DFA更加灵活，但是也正是因为如此，它比较难以在计算机中进行应用...，在后面内容中，我们将看到如何将正则表达式先用NFA表达，然后再将其转换为DFA。...下面我们看看如何将正则表达式转换为NFA，这种算法也叫汤普森构造法。...首先最简单的正则表达式是匹配单个字符例如匹配字符’a’，它对应的NFA如下： 对应稍微复杂一点的表达式，例如识别字符”ab”，那么我们可以分别构造识别a的状态机和识别b的状态机，然后使用一条ε将两个状态机连起来
少数广泛被使用的工具如mawk使用了POSIX NFA引擎（NFA的一种变种）。以高效著称的工具采用了更为高效的DFA引擎。...诸如GNU awk，GNU egrep和Tcl之类的一些工具结合了NFA / DFA两种引擎，将两者的优点结合在一起。 基于不同类型引擎的实现的正则表达式，主要有以下几点差异。...去匹配oneselfsufficient，传统的NFA将匹配 oneself，而POSIX NFA将匹配oneselfsufficient，因为(self)?...由于DFA引擎速度快，但NFA引擎的功能多，因此，混合NFA / DFA引擎试图将二者的优势结合起来。...像GNU egrep和awk只是将两个独立的引擎放一起，然后根据是否使用了NFA特有的功能决定使用哪个引擎。
通过哪个函数，可以把错误转换为异常处理?...正则引擎主要可以分为两大类:一种是DFA,一种是NFA。 一般而论，NFA引擎则搜索更快一些。但是DFA以表达式为主导，更容易操纵，因此一般程序员更偏爱DFA引擎!...NFA表达式主导，DFA文本主导. 可以使用是否支持忽略优先量词和分组捕获来判断引擎类型:支持 NFA,不支持 DFA 正确答案：B 答案分析：正确的说法应该是：一般而论，DFA引擎则搜索更快一些。...(Tokens)、将Tokens转换成简单而有意义的表达式、将表达式编译成Opocdes、顺次执行Opcodes 将PHP代码转换为语言片段(Tokens)、将Tokens转换成简单而有意义的表达式、顺次执行...Opcodes、将表达式编译成Opocdes 将PHP代码转换为语言片段(Tokens)、将表达式编译成Opocdes、顺次执行Opcodes、将Tokens转换成简单而有意义的表达式 将PHP代码转换为语言片段
A 正则引擎主要可以分为两大类：一种是DFA，一种是NFA。 B 一般而论，NFA引擎则搜索更快一些。但是DFA以表达式为主导，更容易操纵，因此一般程序员更偏爱DFA引擎！...C NFA表达式主导,DFA文本主导....D 可以使用是否支持忽略优先量词和分组捕获来判断引擎类型：支持 NFA,不支持 DFA 正确答案：B 答案分析：正确的说法应该是：一般而论，DFA引擎则搜索更快一些。...代码转换为语言片段(Tokens)、将Tokens转换成简单而有意义的表达式、将表达式编译成Opocdes、顺次执行Opcodes B：将PHP代码转换为语言片段(Tokens)、将Tokens转换成简单而有意义的表达式...、顺次执行Opcodes、将表达式编译成Opocdes C：将PHP代码转换为语言片段(Tokens)、将表达式编译成Opocdes、顺次执行Opcodes、将Tokens转换成简单而有意义的表达式
A 正则引擎主要可以分为两大类：一种是DFA，一种是NFA。 B 一般而论，NFA引擎则搜索更快一些。但是DFA以表达式为主导，更容易操纵，因此一般程序员更偏爱DFA引擎！...C NFA表达式主导,DFA文本主导....D 可以使用是否支持忽略优先量词和分组捕获来判断引擎类型：支持 NFA,不支持 DFA 正确答案：B 答案分析：正确的说法应该是：一般而论，DFA引擎则搜索更快一些。...代码转换为语言片段(Tokens)、将Tokens转换成简单而有意义的表达式、将表达式编译成Opocdes、顺次执行Opcodes B：将PHP代码转换为语言片段(Tokens)、将Tokens转换成简单而有意义的表达式...、顺次执行Opcodes、将表达式编译成Opocdes C：将PHP代码转换为语言片段(Tokens)、将表达式编译成Opocdes、顺次执行Opcodes、将Tokens转换成简单而有意义的表达式 D
总的来说， DFA可以称为文本主导的正则引擎 NFA可以称为表达式主导的正则引擎 NFA与DFA工作的区别： 我们常常说用正则去匹配文本，这是NFA的思路，DFA本质上其实是用文本去匹配正则。...NFA VS DFA 首先，正则表达式在计算机看来只是一串符号，正则引擎首先肯定要解析它。NFA引擎只需要编译就好了；而DFA引擎则比较繁琐，编译完还不算，还要遍历出表达式中所有的可能。...这样一来，主流的正则引擎又分为3类：DFA，传统型NFA，POSIX NFA。 正则引擎三国 DFA引擎 DFA引擎在线性时状态下执行，因为它们不要求回溯（并因此它们永远不测试相同的字符两次）。...它将继续回溯（可以确保已找到了可能的最长的匹配之前它们将继续回溯）。...当一个特定字元匹配失败时，正则表达式将试图回溯到扫描之前的位置上，然后进入正则表达式其他可能的路径上。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
