Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。
想改善这个问题吗?更新问题,以便将其作为on-topic用于堆栈溢出。
5年前关闭。
Improve this question
我需要一个可以接收两个正则表达式并确定它们是否同构的库(即是否完全匹配相同的字符串集)
例如a | b与[ab]同构
据我了解,正则表达式可以转换为NFA,在某些情况下可以将其有效转换为DFA。然后,可以将DFA转换为最小DFA,如果我理解正确的话,则该DFA是唯一的,因此可以将这些最小DFA进行比较以得出相等性。我意识到并不是所有的正则表达式NFA都可以有效地转换为DFA(尤其是当它们是从不是真正的“正则”的Perl Regexps生成时),在理想情况下,该库只会返回错误或某种其他表示转换为不可能。
我在网上看到大量关于此操作的文章和学术论文(甚至是一些类(class)的编程作业要求学生这样做),但我似乎找不到能够实现此功能的库。我希望使用Python和/或C/C++库,但可以使用任何语言的库。有人知道这样的图书馆吗?如果不是,是否有人知道我可以用作起点的接近图书馆?
想改善这个问题吗?更新问题,以便将其作为on-topic用于堆栈溢出。
5年前关闭。
Improve this question
我需要一个可以接收两个正则表达式并确定它们是否同构的库(即是否完全匹配相同的字符串集)
例如a | b与[ab]同构
据我了解,正则表达式可以转换为NFA,在某些情况下可以将其有效转换为DFA。然后,可以将DFA转换为最小DFA,如果我理解正确的话,则该DFA是唯一的,因此可以将这些最小DFA进行比较以得出相等性。我意识到并不是所有的正则表达式NFA都可以有效地转换为DFA(尤其是当它们是从不是真正的“正则”的Perl Regexps生成时),在理想情况下,该库只会返回错误或某种其他表示转换为不可能。
我在网上看到大量关于此操作的文章和学术论文(甚至是一些类(class)的编程作业要求学生这样做),但我似乎找不到能够实现此功能的库。我希望使用Python和/或C/C++库,但可以使用任何语言的库。有人知道这样的图书馆吗?如果不是,是否有人知道我可以用作起点的接近图书馆?
最佳答案
还没有尝试过,但是Perl的Regexp:Compare看起来很有希望:如果第一个的语言是第二个的子集,则两个正则表达式是等效的,反之亦然。
关于c++ - 检查两个正则表达式是否相等/同构的库,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/9607062/