例如，我得到一个单词列表，我想从中构建一个简单的正则表达式，至少能匹配所有这些单词（但可能还会匹配更多）。

我希望有一个算法来实现这一点。也就是说，该算法的输入是一个单词列表，输出是一个正则表达式。显然，会有一些限制。比如，如果正则表达式应该匹配无限数量的单词，而我只给它有限数量的单词，那么这个正则表达式将总是匹配更多的单词。或者我需要输入的某种更紧凑的表示。或者我也在考虑给出一个正则表达式作为输入和一个额外的单词列表，我希望得到一个能匹配所有这些单词的正则表达式（可能还会匹配更多）。无论哪种情况，它都应该尝试构建一个尽可能简单的正则表达式。

有哪些技术可以实现这一点？

我被相当误解了。我知道正则表达式背后的基本原理。我知道它是什么。在大多数情况下，我可以很容易地手动为某种语言构建一个正则表达式。但我正在寻找能够做到这一点的算法。

再次以不同的方式表述：

设 L 是一个正则语言。设 M_n 是 L 的一个具有 n 个元素的有限子集。设 M_n 是 M_(n+1) 的子集。

我希望有一个算法 LRE，它接收一个有限的单词集并输出一个正则表达式。我希望它具有以下属性：

lim_n->infinity | diff( LRE(M_n), L ) | = 0

回答：

这个问题在过去十年中已经被研究过。你可以谷歌一下 DFA 学习，下载几篇论文来了解当前的研究状态。

一旦你有了生成正则表达式的 DFA，生成正则表达式就变得简单了。为了避免@FrustratedWithDesign 提到的那些问题，引入了一些条件，比如生成具有最少节点数量的 DFA，从机器学习的角度来看，这类似于为最简单的假设引入正则化条件。