从NFA到DFA的转换正确吗？ - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

自己动手写编译器:从NFA到DFA

int //dfa 节点号码 acceptString string } 这里我们先定义基本的数据结构，在转换的DFA状态机中，它最多包含254个节点，同时状态机只接收来自ascii表中数值从...0到128的字符，这次我们构造的DFA状态机将不像上次构造的NFA状态机那样使用链表结构，这次我们使用跳转表结构，我们将构造一个二维数组dtrans，假设状态节点1接收字符“.”后，跳转到状态节点2，由于字符...在上面代码中我们定义了DFA节点，由于一个DFA节点由一组NFA节点转换而来，因此在它的定义中有一个NFA节点的指针数组。...接下来我们设计用于将NFA转换成DFA的类，其代码为： go type NfaDfaConverter struct { nstates int //当前dfa 节点计数...，这个操作由函数compareNfaSlice和hasDfaContainsNfa完成，如果当前得到的NFA节点集合没有对应的DFA节点，那么就使用addDfaState函数去创建一个新的DFA节点，然后将其加入到

1K2 0

编译原理：第三章词法分析

解释：若对于∑中的任何字α，若存在一条从初态结点s0到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于α，则称α可为DFA M所识别（读出或接受）特别地，若初态结点同时又是终态结点，则空字ε...若对于∑中的任何字α，若存在一条从初态结点s0到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于α，则称α可为NFA 所识别（读出或接受）特别地，若初态结点同时又是终态结点或者存在一条从初态节点到终态节点的空边...，且状态转换函数单值，则该NFA即为DFA。...但是，我们不能说该输入符号串不能被该NFA接受。如果通过尝试的方法，不断试探来确定输入符号串是否可被接受，那么判定的效率将降低。解决的方法是将NFA转换为等价的DFA。...此时，将该表看成是一个状态转换矩阵。（6）将该状态转换矩阵中所有状态子集重新命名，得到状态转换矩阵，其所示的是与给定的NFA N等价的DFA M（未化简的DFA）。

5.3K1 1

您找到你想要的搜索结果了吗？

是的

没有找到

编译原理：2. 词法分析

由此得到的自动机有一个用 a 标记的尾和一个从 b 边进入的头。一般而言，任何一个正则表达式 M 都有一个具有尾和头的 NFA：我们可以归纳地定义正则表达式到 NFA 的转换。...由此得到的结果（在合并了某些等价的 NFA 状态之后）如下图所示： ---- 2.4.2 将 NFA 转换为 DFA ---- 用计算机程序实现确定的有限自动机（DFA）较容易。...继续计算，从状态 5 有一个 \epsilon 转换至状态 8，从状态 8 有一个 \epsilon 转换至状态 6。因此这个 NFA 一定属于状态集合 {2, 5, 6, 8, 15}。...抽象而言，如果 d_j =\text{DFAedge}(d_i,c)，则存在着一条从 d_i 到 d_j 的标记为 c 的边，令 \sum 是字母表。...因为原则上 DFA有 2^n 个状态，但实际上我们一般找到的只有约 n 个状态是从初态可到达的。这一点对避免 DFA 解释器的转换表出现指数级的膨胀很重要，因为这个转换表是编译器的一部分。

1.2K2 1

【计算理论】非确定性有限自动机 ( NFA ) 转换成确定性有限自动机 ( DFA )

有限个字符集 , 长度有限的字符串 ; ③ 转移函数 ( 指令集 ) : 称为转移函数 ; 基于当前的自动机的某个状态 , 将字符集输入到自动机中 , 该自动机转换成一个或多个状态 ,...这个转换就是通过转换函数进行的 , 使用公式描述图片 ④ 起始状态 : 是自动机的开始状态 ; ⑤ 接受状态集 : 是可接受状态 , 是的子集 , 记做..., 与可接受状态相对的是不可接受状态 ; 二、确定性有限自动机 ( DFA ) 与非确定性有限自动机 ( NFA ) 等价确定性有限自动机 ( DFA ) 与非确定性有限自动机 ( NFA...( DFA ) 示例正确的图片 : 图片下图绘制错误 , 暂时作废 , 看第一张图片 ; 图片上图绘制错误 , 暂时作废 , 看第一张图片 ; 字符集 : 将上述非确定性有限自动机 (...NFA ) 转换成确定性有限自动机 ( DFA ) , 需要将非确定性消除 , 只剩下确定性因素 ; 转换过程使用特定算法实现 , 下面会详细描述该算法 ; 表格 : 绘制一个表格 , 表格列分别是

5.6K0 0

面试题（五）

正则的引擎表述错误的是? 正则引擎主要可以分为两大类:一种是DFA,一种是NFA。一般而论，NFA引擎则搜索更快一些。但是DFA以表达式为主导，更容易操纵，因此一般程序员更偏爱DFA引擎!...NFA表达式主导，DFA文本主导. 可以使用是否支持忽略优先量词和分组捕获来判断引擎类型:支持 NFA,不支持 DFA 正确答案：B 答案分析：正确的说法应该是：一般而论，DFA引擎则搜索更快一些。...为了效率数据库可以有多个读库数据库可以用主从做热备数据库不能提供多主多从架构数据库主从是通过日志同步的正确答案：C 答案分析：数据库可以提供多主多从架构。...对参数进行htmlspecialchas过滤对参数使用白名单过滤不允许输入的内容显示到浏览器禁止在js标签内输出用户输入的内容正确答案：A 答案分析：这类过滤可以解决尖括号类型的xss，无法解决...Innodb行锁状态下读不受影响，写会受影响（涉及到的数据）正确答案：A 下列哪个是创建一个每周三01:00~04:00每3分钟执行执行一次的crontab指令？

4951 0

计算理论-有限自动机(FA)

输入字母表：Σ，表示输入的符号集合，用小写字母表示。转移函数：δ，表示从状态q_i到状态q_j的转换条件，用δ(q_i,a)=q_j表示。初始状态：q_0，表示初始状态。...接受状态集合：F，表示接受的状态集合。确定的有限自动机（DFA）定义 DFA是一种确定性的有限自动机，即从初始状态到任意一个接受状态的转换路径都有唯一确定的方向。...（NFA）定义 NFA是一种不确定的有限自动机，即从初始状态到任意一个接受状态的转换路径可能有多条。...记作M=(K, Σ, δ, q0, F) 与DFA的定义类似，只是δ(qi,a)可能有多条路径，表示从状态qi通过输入符号a可以转移到状态**qj**的集合。...多映射例如 δ(q0,0)={q2，q3} 0 1 q₀ {q₁, q₂} {q₁} q₁ {q₁, q₂} {q₀} q₂ {q₂} {q₀} NFA转换成DFA 定理如果语言L可由一个

8071 0

2018 年小米高级 PHP 工程师面试题

5、正则的引擎表述错误的是？ A 正则引擎主要可以分为两大类：一种是DFA，一种是NFA。 B 一般而论，NFA引擎则搜索更快一些。...但是DFA以表达式为主导，更容易操纵，因此一般程序员更偏爱DFA引擎！ C NFA表达式主导,DFA文本主导....D 可以使用是否支持忽略优先量词和分组捕获来判断引擎类型：支持 NFA,不支持 DFA 正确答案：B 答案分析：正确的说法应该是：一般而论，DFA引擎则搜索更快一些。...A：为了效率数据库可以有多个读库 B：数据库可以用主从做热备 C：数据库不能提供多主多从架构 D: 数据库主从是通过日志同步的正确答案：C 答案分析：数据库可以提供多主多从架构。...D：将PHP代码转换为语言片段(Tokens)、将表达式编译成Opocdes、将Tokens转换成简单而有意义的表达式、顺次执行Opcodes 正确答案：C 答案分析：正确答案为C，正确的顺序为：Scanning

5132 0

编译原理（第四版）复习（二）

|AC (A|B)C = AC|BC A(伊姆逊)|(伊姆逊)A = A A* = AA*|(伊姆逊)=A|A* = (A|(伊姆逊))* (A*)* = A* 正规文法到正规式的转换：将正规文法中的每个非终结符表示成关于它的一个正规式方程...依照求解规则：若x=ax|b 或(x=ax+b) 则解为x=a*b; 若x=xa|b 或(x=xa+b) 则解为x=ba*; 正规式到正规文法的转换...正规式与有穷自动机：利用有穷自动机构造词法分析程序的方法是：从语言单词的描述中构造出非确定的有穷自动机；再将非确定的有穷自动机转化成确定的有穷自动机；将其化简为状态最少化的DFA；对DFA的每个状态构造一小段程序将其转化为识别语言单词的词法分析程序...；确定有穷自动机（DFA）：非确定有穷自动机（NFA）： ?...由正规式R构造NFA： ? NFA确定化为DFA的方法： ? DFA的化简： ? 有穷自动机到正规式的转换，参考正规式转换为有穷自动机，基本的就是那三个规则转换；

6323 1

词法分析

正则表达式的定义上面的优先级的顺序是从高到低例子正则语言可以用正则表达式定义的语言叫做正则语言或正则集合正则文法与正则表达式等价对任意正则文法G，存在定义同一语言的正则表达式r...有穷自动机的分类又穷自动机分成两类：确定的FA——DFA，非确定的FA——NFA DFA例子非确定的有穷自动机（NFA）是从状态S出发，沿着标记位a的边不止一个路径 NFA例子等价性...但是从计算机的角度来说，DFA比较好实现带有“生成ε边”的NFA 从上面可以看出，A状态可以在不接收任何字符的情况下进入B状态，但进入B状态之后就不能再接收0号信号。...从正则表达式到有穷自动机正则表达式（RE）直接到DFA是不太好实现的，所以我们通过NFA 根据RE(正则表达式)构造NFA 例子先画起始状态和终止状态把正则表达式分成多个子表达式然后对各个子表达式进行转换工作...从NFA到DFA的转换模仿上面怎么写的就可以。

5642 0

2018年小米高级 PHP 工程师面试题（模拟考试卷）

5、正则的引擎表述错误的是？ A 正则引擎主要可以分为两大类：一种是DFA，一种是NFA。 B 一般而论，NFA引擎则搜索更快一些。...但是DFA以表达式为主导，更容易操纵，因此一般程序员更偏爱DFA引擎！ C NFA表达式主导,DFA文本主导....D 可以使用是否支持忽略优先量词和分组捕获来判断引擎类型：支持 NFA,不支持 DFA 正确答案：B 答案分析：正确的说法应该是：一般而论，DFA引擎则搜索更快一些。...A：为了效率数据库可以有多个读库 B：数据库可以用主从做热备 C：数据库不能提供多主多从架构 D: 数据库主从是通过日志同步的正确答案：C 答案分析：数据库可以提供多主多从架构。...：将PHP代码转换为语言片段(Tokens)、将表达式编译成Opocdes、将Tokens转换成简单而有意义的表达式、顺次执行Opcodes 正确答案：C 答案分析：正确答案为C，正确的顺序为：Scanning

7953 0

编译原理:NFA转DFA

工作原理 DFA 从初始状态开始,根据输入符号和状态转移函数不断地转移状态。当输入字符串处理完毕后,如果 DFA 处于接受状态集合中的某个状态,则认为该字符串被 DFA 接受；否则,该字符串被拒绝。...,NFA)也是一种计算模型,与 DFA 相比,它在状态转移上具有不确定性。...如果存在一条从初始状态到某个接受状态的路径,使得沿着该路径处理完整个输入字符串,则认为该字符串被 NFA 接受。...转 DFA 步骤步骤 1：确定初始状态步骤 2：状态转移计算步骤 3：接受状态确定步骤 4：重复步骤 2 和 3 示例假设我们有一个简单的 NFA,其状态转移表如下：最终得到的 DFA 状态转移表如下...：通过以上步骤,我们成功地将 NFA 转换为了 DFA。

6821 0

DFA和NFA

2.DFA和NFA 引用理解DFA和NFA 正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。...一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。 DFA与NFA机制上的不同带来5个影响： 1....由此可知，要让NFA正确工作，应该使用 /perlman|perl/ 模式。通过以上例子，可以理解为什么NFA是最左子式匹配，而DFA是最长左子式匹配。...有可能对两个给定正则表达式写一个算法来判定它们所描述的语言是否本质上相等，简约每个表达式到极小确定有限自动机，确定它们是否同构（等价）。这种冗余可以消减到什么程度?...我们可以找到仍有完全表达力的正则表达式的有趣的子集吗? Kleene 星号和并集明显是需要的，但是我们或许可以限制它们的使用。这提出了一个令人惊奇的困难问题。

1.1K2 0

Stanford公开课《编译原理》学习笔记(1~4课)

：后继状态为自身后继状态只有一个后继状态有多个如果每次转换后的后继状态都是唯一的，则称为DFA（确定有限自动机），如果后继状态可能有多个则称为NFA（不确定有限状态机）。...正则表达式是可以转换为NFA形式的，或许你已经在一些可视化正则表达式的网站上[https://regexper.com ]见过类似的形式。...下图比较清晰地展示了从正则表达式到NFA状态图的转换规则(Regular expressions——>NFA)： ?...如果一个DFA和一个NFA能够识别的字符集是一致的，则称它们为等价的，对于任意NFA，一定存在一个DFA与其等价，由NFA构建DFA的过程被称为DFA的确定化，也就是NFA——>DFA的过程。...状态集合，使用矩阵记录每个ε -closure集合转换前后的集合，最后对整个状态转移矩阵进行标记重命名，就可以得到一个DFA，事实上转化后的DFA中的每一个状态，就是NFA中的一个ε -closure

9482 0

【计算理论】计算理论总结 ( 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ) ★★

文章目录一、非确定性有限自动机 ( NFA ) 转为确定性有限自动机 ( DFA ) 二、转换方法与要点一、非确定性有限自动机 ( NFA ) 转为确定性有限自动机 ( DFA ) ---- 确定性有限自动机...( DFA ) 与非确定性有限自动机 ( NFA ) 之间是相互等价的 ; 确定性的有限自动机 ( DFA ) 可以看作是非确定性有限自动机 ( NFA ) ; 确定性有限自动机给定一个输入 ,...确定性有限自动机 ( DFA ) 就是特殊的非确定性有限自动机 ( NFA ) ; 可以证明非确定性有限自动机 ( NFA ) , 必定有一个确定性有限自动机 ( DFA ) 与其等价 ; 参考博客...转换方法 : 从起始状态开始推演运行 , 列出所有的分支步骤 , 注意计算分叉节点 , 会产生多个后续状态 , 此时就生成了新的状态 , 这些新的状态就是非确定性有限自动机转换成的确定性有限自动机的...接受状态 : 如果最终的 DFA 的新状态集合中 , 包含 NFA 的接受状态 , 那么该新状态就是接受状态 ; 4.

1.9K0 0

ReDoS：正则也许会让你的系统更脆弱

首先，来看一个简单的正则表达式—— a(bb)+a ，它可以转换成以下两种表达： DFA NFA 上面两张图能够很清晰地表现出二者的不同： DFA 中，每一个状态在接收到输入时，下一个状态都是确定的...理论上，每一条正则表达式都可以等同转换成一个 NFA 状态机，那么如果使用 NFA 进行匹配，如何处理猜测分支就很重要了。下面我们来看一个简单遍历猜测的例子。...可以转换成 Thompson 构造，图示：稍微做一些解释： q 是开始，f 是结束，白圈是状态，连线是流转 ε 代表着无输入通过以上的结构，Thompson NFA 匹配的时间复杂度为，空间复杂度为...说来有趣，Thompson NFA 构造法应该是编译原理的基础概念，DFA 方法从概念上也是比较简单，为什么当前的主流语言没有采用，反而采用了一个带有回溯的、效果远逊的版本？...可以从上文得知，正则匹配的实现首先需要兼容原来的使用方式，而当时开发者并未了解 NFA 模拟方法，而是自己从零实现了一个回溯方法，并且被广泛地传播开了。

1.6K4 0

正则引擎设计与实现——基于子集构造法

如果人工进行分析(不考虑编码实现), 不难看出, 如果从 NFA 的起点出发, 存在如下状态转换: 图片换言之, 1,2,3 这三个节点都是 NFA 首个状态, 于是, 得到如下 NFA : 下一步...从表达的语义来看,DFA 与 NFA 并没有差别,如上例的 NFA 的转换: 其对应的 DFA 转换: 事实上, 两者都表达了 "起点处输入a可能到达1或2"....但是在表达形式上, NFA 将这种二义性(或者说多种可能性)表现在转换上了; 而与之不同, DFA 将二义性表达在状态里, 多种可能性被聚合在状态里, 消除了转换的二义性....前文中讲 NFA 转 DFA 时, 其实忽略一个现实: "转换可以是针对一个范围的输入" ....针对这种情况, 在将 NFA 转换 DFA 时, 需要设计一个算法, 消除 NFA 的存在交集的转换的二义性, 算法过程如下: 上例中, 起点处存在如下 4 个转换: 我们把每个转换的输入区间看作一个集合

5861 0

【计算理论】计算理论总结 ( 非确定性有限自动机 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 无条件跳转到...接受任何字符都是空集 \{\varnothing \} ; 最终的 DFA 如下 : 详细推理过程 : 【计算理论】非确定性有限自动机 ( NFA ) 转换成确定性有限自动机 ( DFA ) 二...、NFA 转 DFA 示例 2 ---- 将下图的非确定性有限自动机 NFA 转为确定性有限自动机 DFA ; NFA 的状态集 \rm \{ 1,2,3 \} , 字符集 \rm \{ a,...DFA ; NFA 的状态集 \rm \{ 1,2 \} , 字符集 \rm \{ a,b \} ; 从起始状态 1 开始分析 , \rm \{1\} 状态下读取 \rm a

8570 0

从0到1打造正则表达式执行引擎(二)

在上篇博客从0到1打造正则表达式执行引擎(一)中我们已经构建了一个可用的正则表达式引擎，相关源码见https://github.com/xindoo/regex，但上文中只是用到了NFA，NFA的引擎建图时间复杂度是...图示分别是一个NFA和DFA，上图之所以是NFA是因为它有节点具备不确定性，比如0节点，在输入"a"之后它分别可以到0 1 2 节点。...由于NFA的非确定性，在面对一个输入的时候可能有多条可选的路径，所以在一条路径走不通的情况下，需要回溯到选择点去走另外一条路径。...然后我们分别在dfa2 dfa3上执行步骤三，找不到新节点，但会找到几条新的边，补充如下，至此我们就完成了对 **a(b|c)*** 对应NFA到DFA的转化。 ?...节点列表到DFA节点的转化和查找，具体如下。

8002 0

编译原理从入门到放弃

NFA与DFA的定义 NFA转化为DFA 正规表达式与有限自动机之间的转化 4.1 NFA与DFA的定义 4.1.1确定的有限自动机（DFA）的定义一个有穷自动机M是一个五元组： M=（S，∑，f，S0...，Z） S是一个有限状态集合 ∑是一个字母表，它的每个元素称为一个输入字符 f是一个从S✖∑至S的单值部分映射，f（S，a）=s‘ 意味着：当现行状态为s，输入字符为a时，将状态到下一状态s‘。...是一个从S✖∑至S的单值部分映射，f（S，a）=s‘ 意味着：当现行状态为s，输入字符为a时，将状态到下一状态s‘。...4.2 NFA转化为DFA 例6：已知不确定的有限自动机（NFA）如图所示，采用子集法将其确定化为DFA的过程如下表示： I I0 I1 {S,1,2,3} {1,3,4,5,Z} {2,3} {1,3,4,5...（NFA）的状态转换图如下图所示，该NFA等价的正规式是____。

1.2K2 0

深入正则表达式(3):正则表达式工作引擎流程分析与原理释义

总的来说， DFA可以称为文本主导的正则引擎 NFA可以称为表达式主导的正则引擎 NFA与DFA工作的区别：我们常常说用正则去匹配文本，这是NFA的思路，DFA本质上其实是用文本去匹配正则。...从整个字符串第一个字符开始f开始查找t，查找到t后，定位到t，以知其后为o，则去查看正则表达式其相应位置后是否为o，如果是，则继续（以此循环)，再去查正则表达式o后是否为n（此时淘汰knite分支），再后是否为...这样一来，主流的正则引擎又分为3类：DFA，传统型NFA，POSIX NFA。正则引擎三国 DFA引擎 DFA引擎在线性时状态下执行，因为它们不要求回溯（并因此它们永远不测试相同的字符两次）。...因为上一次是从第一个字符a开始匹配，所以下一个位置当然就是从第二个字符b开始咯。...下面是一个正则表达式处理的基本步骤：第一步：编译当你创建了一个正则表达式对象之后（使用一个正则表达式直接量或者RegExp构造器），浏览器检查你的模板有没有错误，然后将它转换成一个本机代码例程，用于执行匹配工作

2.5K0 0

点击加载更多

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭