是否有一种算法可以确定一种常规语言是否与另一种常规语言匹配的输入匹配？
是否有一种算法可以确定一种常规语言是否与另一种常规语言匹配的输入匹配？
提问于 2010-09-03 02:48:49
假设我们有正则表达式：
- Hello W.*rld
- Hello World
- .* World
- .* W.*
我希望最小化匹配任意输入所需的正则表达式的数量。
为此，我需要确定一个正则表达式是否与另一个表达式匹配的任何输入匹配。这有可能吗？
Billy3
回答 4
Stack Overflow用户
回答已采纳
发布于 2010-09-03 03:32:00
任何正则表达式都可以链接到DFA -您可以最小化DFA，并且由于最小形式是唯一的，您可以决定两个表达式是否相等。Dani Cricco指出了Hopcroft O(n log n)算法。Hopcroft和Craft提出了另一种改进算法，该算法测试O(n)中两个DFA的等价性。
为了对这个问题进行一个很好的调查和一个有趣的方法，我推荐arXiv的论文Testing the Equivalence of Regular Languages。
稍后编辑:如果你对包含而不是正则表达式的等价性感兴趣，我看到了一篇可能感兴趣的论文：Inclusion Problem for Regular Expressions -我只浏览了一下，但它似乎包含了一个多项式时间的算法来解决这个问题。
Stack Overflow用户
发布于 2010-09-03 03:12:25
是。
两种正则语言的等价性问题是可以判定的。
算法示意图：
- 最小化两个DFAs
- 检查它们是否同构
Stack Overflow用户
发布于 2010-09-03 03:18:07
当然可以！正则表达式可以表示为FSM (有限状态机)，并且在技术上有无限数量的FSM可以识别相同的字符串。
同构是描述两个FSM是否等价的名称。有几种算法可以最小化FSM。例如，在n个状态自动机上，Hopcroft minimization algorithm可以最小化O( n )中的两个有限状态机。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3630203
复制相关文章
相似问题