生成与某些输入集匹配的正则表达式是否是可解决的问题？

Question

我提供了一些包含已知分隔数量的文本块的输入集.

我想创建一个程序,自动生成一个或多个正则表达式,每个正则表达式匹配输入集中的每个文本块.

我看到一些相对简单的方法来实现暴力搜索.但我不是编译器理论方面的专家.这就是我很好奇的原因:

1)这个问题可以解决吗？或者有一些原则不可能做出这样的算法？

2)是否有可能实现该算法的多项式复杂度并避免暴力强制？

Answer 1

".*"是一个或多个正则表达式,它将匹配输入集中的每个文本块.;-)

Answer 2

问题是,有大量的正则表达式(实际上是无限数)将匹配给定的输入集.它们的范围从非常"贪婪"的表达,将匹配一切

.*

非常非"贪婪"的表达式,它将与输入集完全匹配

InputA OR inputB OR inputC etc

在这两者之间,您可以通过各种方式改变表达式,使其变得越来越贪婪(例如,用与任何数字匹配的表达式替换特定数字等).

你必须告诉我们更多关于这个问题的信息,让我们知道在那个可能的答案范围内哪个是正确答案;)