程序员经验分享-hwhale

将有限状态机转换为正则表达式

2024-03-03

有没有工具（或算法）来转换有限状态机 into a 正则表达式?

（不是相反，那很容易）。


有几种算法可以执行此任务：Brzozowski 和 Mc Cluskey 的“状态消除法”、线性方程组的求解、McNaughton 和 Yamada 的方法等。它们在自动机和有理式 http://arxiv.org/abs/1502.03573作者：雅克·萨卡罗维奇。

状态消除法尤其容易理解。关键思想是您将构建一个由理性（又称正则）表达式而不是字母标记的自动机。首先，确保您有一个初始状态和一个最终状态（如果需要，您可以添加新状态和自发转换）。然后选择一个状态s进行消除，如下图的状态1。

然后考虑所有对 (p, q)，其中 p 是前驱（从该状态开始转移到达图中的 s, 0），q 是后继（状态 2）。对于每个这样的对 (p, q)，添加从 p 到 q 的转换，其标记为 E(p, q) + E(p, s)E(s, s)*E(s, q)，其中 E(p, q) + E(p, s)E(s, s)*E(s, q) , s) 表示“标记从 p 到 s 的转换的表达式。处理完所有对 (p, q) 后，删除状态 s。在前面的示例中：

这样做直到消除所有内部状态（即保留初始状态和最终状态），然后读取从初始状态到最终状态的转换结果（此处为 d+ab*c）。

你可以使用这个算法来玩弄Vcsn http://vcsn.lrde.epita.fr，有理表达式和自动机的工具。这是一个完整的示例，您可以在以下位置复制：VCSN沙箱 http://vcsn-sandbox.lrde.epita.fr.

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

regex

Algorithm

fsm

将有限状态机转换为正则表达式 的相关文章

  • 如何将无向图转换为 DAG？

    The 维基页面 http en wikipedia org wiki Directed acyclic graph Relation to other kinds of graphs says 任何无向图都可以通过为其顶点选择总顺序并将每

  • 寻找距离原点最近的 100 颗恒星的算法

    首先让我提出正确的问题 问 有一个文件包含超过一百万个点 x y 每个点代表一颗星星 a b 处有一颗行星地球 现在 任务是构建一种算法 返回距离地球最近的 100 颗恒星 您的算法的时间和空间复杂度是多少 这个问题在各种采访中被问过很多次

  • 为什么正则表达式中有四个反斜杠？

    d 1 2 我有上面的正则表达式 我知道字符串解析器会删除两个反斜杠 留下我们 d 以1为元字符 无关的功能是什么 我以前没有正则表达式的经验 或者字符串模式本身就是 反斜杠 最多出现两次的整数 我错过了什么吗 反斜杠转义其他反斜杠以及特殊

  • 找到一系列间隔的最有效分组

    我有一个应用程序 其中有一系列不重叠的固定宽度间隔 每个间隔都有一个给定的键 每个间隔具有相同的宽度 并且可以存在连续的间隔 本质上 我想以最小化单独间隔的数量的方式对间隔和键进行分组 这可以通过合并具有相同键的连续间隔或查找匹配间隔并将它

  • 用于检查字符串是否至少包含 3 个字母数字字符的最有效的正则表达式

    我有这个正则表达式 a zA Z0 9 3 我用它来查看字符串中是否至少包含 3 个字母数字字符 似乎有效 它应该匹配的字符串示例 a3c 0 c 8 9 9d 但是 我需要它更快地工作 有没有更好的方法使用正则表达式来匹配相同的模式 编辑

  • 如何在Python中的正则表达式中匹配字符串列表中的任何字符串？

    假设我有一个字符串列表 string lst fun dum sun gum 我想创建一个正则表达式 在其中的某个点 我可以匹配该列表中的任何字符串 在一个组内 如下所示 import re template re compile r el

  • 由周期表元素形成的最大单词的算法

    我想为以下问题场景编写一个算法 根据元素周期表元素的名称 找到可以组成的最大单词 符号如Na Ne等应被视为单个元素 这是在一家知名公司的求职面试中被问到的 有人可以帮我解决这个问题吗 我认为更好的方法是检查字典中的每个单词 看看是否可以从

  • 使用 .htaccess 重定向到动态相对路径？

    是否可以使 htaccess 理解 动态相对路径并正确重定向到它们 我的设置如下 http domain com htroot aaa xyz http domain com htroot bbb xyz http domain com h

  • 使用 R 从字符串中提取函数参数

    最好使用stringr包 我想创建一个函数extract 以字符串向量作为参数 vec lt c div span icon hospital user i18n t Enrolments or i18n t Paper a string

  • 无需构建树即可预测霍夫曼压缩比

    我有一个二进制文件 我知道其中每个符号出现的次数 如果我要使用霍夫曼算法压缩它 我需要预测压缩文件的长度 我只对假设的输出长度感兴趣 而不对单个符号的代码感兴趣 因此构建霍夫曼树似乎是多余的 作为一个例子 我需要得到类似的东西 包含 4 个

  • 从三点求圆心的算法是什么？

    我在圆的圆周上有三个点 pt A A x A y pt B B x B y pt C C x C y 如何计算圆心 在Processing Java 中实现它 我找到了答案并实施了一个可行的解决方案 pt circleCenter pt A

  • JavaScript 正则表达式两个标签之间的多行文本

    我编写了一个正则表达式来从 HTML 中获取字符串 但似乎多行标志不起作用 这是我的模式 我想将文本输入h1 tag var pattern div class box content 5 h1 lt lt h1 gt mi m html

  • Angular 2：使用正则表达式进行数字验证

    我正在尝试验证 IE 11 中的数字字段

  • 分而治之策略来确定列表中是否有超过 1/3 的相同元素

    我正在使用分治算法来确定列表中是否有超过 1 3 的元素相同 例如 1 2 3 4 不 所有元素都是唯一的 1 1 2 4 5 是的 其中 2 个是相同的 没有排序 是否有分而治之的策略 我陷入了如何划分的困境 def is valid i

  • 以任意顺序匹配可选捕获组

    在解析用户输入的许多情况下 用户有机会向输入添加几个可选标志 这些标志应该以任何顺序接受 如何使用正则表达式对其进行解析 以便每个标志都位于它自己的捕获组中 如果存在 例如 有一个必需的令牌a 然后是 3 个可选标记 可以按任何顺序出现b

  • 需要正则表达式（使用 C#）将所有空白压缩为单个空白

    我需要将文档中的多个空格替换为单个空格 每次迭代 无论它们是空格 制表符还是换行符 任何类型的空格的任何组合都需要被截断为单个空格 假设我们有字符串 Hello t t n t n world 其中 t 和 n 分别代表制表符和换行符 那么

  • 包围一组点的多边形

    我有一组 S 点 2D 由 x 和 y 定义 我想找到 P 包围该组所有点的最小 含义 具有最少数量的点 多边形 P 是S 有没有已知的算法来计算这个 我在这个领域缺乏文化令人惊讶 感谢您的帮助 对于这个问题有很多算法 它被称为 最小边界框

  • 为什么这个没有特殊字符的正则表达式会匹配更长的字符串？

    我正在使用此方法来尝试查找匹配项 例如 Regex Match A2 TS OIL TS OIL RegexOptions IgnoreCase Success 我得到了真实的结果 我很困惑 我认为这应该返回 false 因为模式中没有特殊

  • 使用并集查找（又名不相交集）检测图是否是二分图

    我正在 Spoj 上做一个问题 基本上可以简化为检测图是否是二分图 我正在尝试使用 dfs 为图表着色 但它太慢了 有人评论这个 没有 bfs 没有 dfs 没有二部图 简单的并查集就可以做到 确实速度很快 提示 1 偶数长度的环不会影响两

  • Java 正则表达式中的逻辑 AND

    是否可以在 Java Regex 中实现逻辑 AND 如果答案是肯定的 那么如何实现呢 正则表达式中的逻辑 AND 由一系列堆叠的先行断言组成 例如 foo bar glarch 将匹配包含所有三个 foo bar 和 glarch 的任何

随机推荐

热门标签