Bil*_*eal 18 regex theory computer-science
假设我们有正则表达式:
我想最小化匹配任意输入所需的正则表达式的数量.
为此,我需要查找一个正则表达式是否与另一个表达式匹配的任何输入匹配.那可能吗？
Billy3
Law*_*nce 12
任何正则表达式都可以链接到DFA - 您可以最小化DFA,并且由于最小形式是唯一的,因此您可以决定两个表达式是否相同.Dani Cricco指出了Hopcroft O(n log n)算法.Hopcroft和Craft还有另一种改进的算法,用于测试O(n)中两个DFA的等价性.
对于这个问题的一个很好的调查和一个有趣的方法,我推荐了arXiv的测试正则语言的等价性的论文.
稍后编辑:如果你对正则表达式的包含而不是等价感兴趣,我会遇到一篇可能感兴趣的论文:正则表达式的包含问题 - 我只是略过它但它似乎包含一个多项式时间算法问题.