是否存在可以确定一种常规语言是否匹配任何输入，另一种常规语言匹配的算法？

本文介绍了是否存在可以确定一种常规语言是否匹配任何输入，另一种常规语言匹配的算法？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

假设我们有正则表达式：

Let's say we have regular expressions:

• Hello W. * rld
• Hello World
• 。*世界
• 。* W。*

• Hello W.*rld
• Hello World
• .* World
• .* W.*

我想最大程度地减少匹配任意输入所需的正则表达式。

I would like to minimize the number of regexes required to match arbitrary input.

为此，我需要确定一个正则表达式是否与任何由匹配的输入匹配另一个表达。

To do that, I need to find if one regular expression matches any input matched by another expression. Is that possible?

Billy3

推荐答案

任何正则表达式都可以链接到DFA-您可以最小化DFA，并且由于最小形式是唯一的，因此您可以决定两个表达式是否相等。 Dani Cricco指出了Hopcroft O（n log n）算法。 Hopcroft和Craft还提供了另一种改进的算法，用于测试O（n）中两个DFA的等效性。

Any regular expression can be linked to a DFA - you can minimize the DFA and since the minimal form is unique, you can decide whether two expressions are equivalent. Dani Cricco pointed out the Hopcroft O(n log n) algorithm. There is another improved algorithm by Hopcroft and Craft which tests the equivalence of two DFAs in O(n).

对此问题进行了很好的调查并找到了一种有趣的方法，我推荐来自arXiv的论文测试常规语言的等效性。

For a good survey on the matter and an interesting approach to this, I reccomend the paper Testing the Equivalence of Regular Languages, from arXiv.

以后的编辑：如果您对包含而不是等价于正则表达式感兴趣，我遇到了一篇可能感兴趣的论文：正则表达式的包含问题-我只是略过了这个问题，但是似乎包含多项式时间算法。

Later edit: if you are interested in inclusion rather than equivalence for regular expressions, I have come across a paper that might be of interest: Inclusion Problem for Regular Expressions - I have only skimmed through it but it seems to contain a polynomial time algorithm to the problem.