问题标签 [dfa]

有没有办法找出两个任意正则表达式是否等价？对我来说看起来很复杂，但可能有一些 DFA 简化机制之类的？

是否有将正则表达式转换为NFA的好库？我看到很多关于该主题的学术论文，这些论文很有帮助，但对工作代码的影响不大。

我的问题部分是出于好奇，部分是由于实际需要在我正在开发的生产系统上加快正则表达式匹配。尽管为了学习而探索这个主题可能很有趣，但我不确定它是否是加速我们的模式匹配的“实用”解决方案。我们是一家 Java 商店，但很乐意提供任何语言的优质代码。

编辑：

有趣的是，我不知道 Java 的正则表达式已经是 NFA。这篇论文的标题让我不相信。顺便说一句，我们目前正在 Postgres 中进行正则表达式匹配；如果简单的解决方案是将匹配移动到 Java 代码中，那就太好了。

我希望能够计算所有字符的集合，这些字符可能与给定的java.util.regex.Pattern. 更正式地说，给定 DFA 等价于某个正则表达式，我想要从起始状态开始的所有传出转换的集合。

一个例子：

该集合first应包含以下元素：

有任何想法吗？我很清楚我可以自己构建 DFA 并以这种方式确定相关状态，但我想避免这种麻烦（阅读：这对我来说不值那么多）。请注意，我的宿主语言实际上是 Scala，因此我可以访问所有核心 Scala 库（值得一提）。

我有一个代表正则表达式的给定 DFA。我想将 DFA 与输入流进行匹配并取回所有可能的匹配项，而不仅仅是最短最长的匹配项。

例如：

正则表达式：a*ba|baa

输入：aaaaabaaababbabbbaa

结果：

1. 啊啊啊啊
2. 阿巴
3. 巴
4. 咩

有谁知道包含典型编译器课程的在线课程/大学讲座？我有计算理论，但不幸的是我的学校没有提供编译器构造课程。

我知道那里有讲座；我希望能推荐一些特别好的产品。

另外，是否有适合该领域新手的书籍？至少除了龙书之外的东西。初学者水平还可以，我知道市面上有很多中高级教材。

谢谢！

我有这个输入文件：

第一行代表测试用例的数量。

每个测试用例以 3 个整数开头，第一个是自动机的状态数，接下来是字母表中的符号数，然后是最终状态数。

下一行是字母表。这些符号一起出现。

然后有许多行等于描述转换函数的状态数。这组线的第一行表示自动机 (qo) 中第一个状态的转换函数，第一个元素表示当字母表中的第一个符号进入该状态时达到的状态，依此类推。我无法从原始问题陈述中理解这一点。这是我来看它的最简单的方法：

这些行：

平等的：

然后有一行说明自动机的最终状态。

然后是一行，说明哪个是初始状态以及将出现多少输入字符串。

然后是输入字符串的行。

这个程序的输出应该是：

它应该说明字符串是被接受还是被拒绝以及它在哪个状态下结束。

到目前为止，我只使用输入对工作进行了编码。

我不知道如何最方便地表示自动机。我应该创建一个 Graph 类吗？我应该简单地使用数组吗？我会对数组应用什么逻辑？

编辑这是我根据 MICHAEL BORGWARDT 的建议生成的代码。转换工作，但我不知道为什么字符串在处理时会卡在状态 0 上。 **

是否有任何（免费）Java 正则表达式引擎可以将正则表达式编译为 DFA，并在匹配 DFA 时进行组捕获？

我找到了 dk.brics.automaton 和 jrexx，它们都编译为 DFA，但似乎都无法进行组捕获。虽然我发现的其他引擎似乎可以编译为 NFA。

问题：提供了一个大的静态字符串列表。由数据和通配符元素（* 和 ?）组成的模式字符串。这个想法是返回所有匹配模式的字符串 - 很简单。

当前解决方案：我目前正在使用线性方法扫描大列表并将每个条目与模式进行匹配。

我的问题：是否有任何合适的数据结构可以存储大列表以使搜索的复杂性小于 O(n)？

也许类似于suffix-trie的东西？我也考虑过在哈希表中使用二元组和三元组，但是根据返回的单词列表和模式的合并来评估匹配所需的逻辑是一场噩梦，而且我不相信它是正确的方法。

希望你能帮我解决这个问题......

我有一个主要问题是''​​如何判断正则表达式是否会被NFA和/或DFA接受？

例如。我的问题是哪个正则表达式是等价的？解释... 1.(a+b)**b(a+b)**b(a+b)*

2.呸呸呸*

3.a ba b(a+b)*

我们是否必须绘制NFA和DFA然后通过最小化算法找到？如果我们这样做，那么我们如何知道 NFA/DFA 接受哪个正则表达式，以便我们可以从答案开始？它是如此混乱....

第二个是一个非常相似的问题，问题要求我表明语言 (a^nb^n|n>1} 不被 DFA 接受...grrrrr...我怎么知道这个？（顺便说一句，这是一个所有字符串的集合，其中多个 a 后跟相同数量的 b)....

我希望我解释清楚......

我们如何使用交集方法组合两个 dfa？