问题标签 [nfa]

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

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

编辑：

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

有人知道 Python（任何版本）是否使用 NFA（非确定性有限自动机）来评估正则表达式还是使用其他机制？如果可用，请提供链接/参考。

可以有一个 NFA 决定实数吗？

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

我有一个主要问题是''​​如何判断正则表达式是否会被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)....

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

您能否推荐一个用 F# 编写的开源库，它为 FA 构造和基本算法（NFA 到 DFA 转换、FA 最小化......）提供通用类型？

我目前正在研究扫描仪生成器。生成器已经可以正常工作了。但是当使用字符类时，算法变得非常慢。

扫描仪生成器为 UTF8 编码文件生成扫描仪。应该支持全范围的字符（0x000000 到 0x10ffff）。

如果我使用大型字符集，例如任何运算符 '.' 或 unicode 属性 {L}，nfa（以及 dfa）包含很多状态（> 10000）。因此，将 nfa 转换为 dfa 并创建最小 dfa 需要很长时间（即使输出的最小 dfa 仅包含几个状态）。

这是我当前创建 nfa 的字符集部分的实现。

有谁知道如何更有效地实现该功能以仅创建必要的状态？

编辑：

更具体地说，我需要一个函数，例如：

将字符 (int) 转换为 UTF8 编码 byte[] 的辅助函数定义为：

我是这么想的，因为上限是 2^n，并且鉴于它们都是有限机器，n 状态 NFA 和具有 2^n 或更少状态的 DFA 的交集将是有效的。

我在这里错了吗？

是否存在用于描述 NFA 或 DFA 的转换表的标准语法？

我正在寻找关于 DFA 与 NFA 引擎之间差异的非技术解释，基于它们的功能和限制。

晚安，

假设我有一个实现 NFA/DFA 的类，它的转换存储在 .NET Dictionary 结构中，它接受一个输入单词并识别一组可从输入中以某种方式派生的单词。此外，假设自动机是一个通用模板，它可以应用于相同长度的不同单词，只需重新标记过渡字符。在 Dictionary 中对转换函数进行编码以便在运行时根据输入单词的字符重新标记转换函数的最佳方法是什么？

非常感谢你。