库检查两个正则表达式是否相等/同构

我需要一个库，它将采用两个正则表达式并确定它们是否是同构的（即匹配完全相同的一组字符串）例如a | b是同构于[ab]库检查两个正则表达式是否相等/同构

据我所知，正则表达式可以转换为NFA，在某些情况下，它可以高效地转换为DFA。然后可以将DFA转换为最小DFA，如果我理解正确，则该DFA是唯一的，因此可以比较这些最小DFA的平等性。我意识到，并非所有正则表达式NFA都可以有效地转换为DFA（特别是当它们是从Perl Regexps生成的时，它们并非真正的“常规”），在这种情况下，理想情况下库会返回错误或其他指示不可能。

我在网上看到大量文章和学术论文关于这样做（甚至一些程序设计任务，要求学生这样做），但我似乎无法找到实现此功能的库。我更喜欢Python和/或C/C++库，但任何语言的库都可以。有谁知道这样的图书馆？如果不是，有人知道一个图书馆可以接近我可以用作起点吗？

来源

2012-03-07 user1255384

这是功课吗？ :-) – 2012-03-07 18:35:32

不是。它是一个研究项目的一部分。但这不是项目的核心，所以如果我不需要，我宁愿不花时间推出自己的产品。 – user1255384 2012-03-07 18:37:34

我只是在开玩笑。这个问题问得好。所以+1。 – 2012-03-07 18:43:39

还没有尝试过，但Perl的Regexp:Compare看起来很有前途：如果第一个语言的语言是第二个语言的子集，并且反之亦然，则两个正则表达式是等价的。

来源

2012-03-07 20:33:48 user1071136

我检查了它，它看起来像它正是我想要的。我不能从粗略的代码中看出它是如何做到的，但它在我测试过的所有简单情况下都能正常工作。感谢指针！ – user1255384 2012-03-08 18:40:34

对于Java的brics automaton library也支持这一点。您可以将正则表达式转换为DFA，并检查它们是否相同。

来源

2013-07-17 22:14:16 ChrisBlom

库检查两个正则表达式是否相等/同构

回答

相关问题