regex - 将接受一组字符串的正则表达式 A 转换为接受 A 匹配的字符串的所有前缀的正则表达式

Question

给定任何正则表达式 A，有没有办法将其转换为另一个正则表达式 B，它接受 A 接受的所有字符串和字符串的前缀。

例如，如果 /apple/ 是给定的正则表达式，是否有通用方法将其转换为 /a|ap|app|appl|apple/

Answer 1

如果您正在谈论正式的正则表达式（即描述正则语言的正则表达式），那么这里有一个将正则表达式转换为接受前缀的正则表达式的过程。

任何正则表达式都有一个DFA；这是 DFA /apple/（省略了到故障状态的转换）：

要生成匹配此 DFA 接受的字符串前缀的 DFA，如果它们位于导致原始 DFA 中接受状态的路径上，则将状态转换为接受状态：

有几种方法可以从 DFA 中读取正则表达式。如果我们使用状态移除技术，我们会得到以下 DFA：

这对应于正则表达式/a|ap|app|appl|apple|/，加上空字符串（因为空字符串是任何正则表达式的前缀）。

这个apple例子很简单，但同样的技术可以用于更复杂的正则表达式。例如，考虑/(00)*1(00|1)*/：

此 DFA 接受字符串00100但不接受0010101. 在将适当的状态转换为最终状态并组合两个相同的状态后，我们有

这相当于

我们可以从中读取正则表达式/(00)*(0?|1(1|00)*0?)/，其中包括空字符串。

此正则表达式拒绝00101，因为它会导致原始 DFA 转换为失败状态，但接受“0”和“00”，因为这些字符串不会导致原始 DFA 进入失败状态。

Answer 2

显然可以通过转换为有限状态机，将所有状态更改为接受状态并转换回来来完成，如@JoshRosen 的回答所示。

这是一个更直接的算法。为简单起见，我将在这里假设正则表达式的正式定义。因此，表达式是从空字符串、文字字符和运算符连接、交替 ('|') 和 Kleene 星号 ('*') 递归构建的。我还将包括运算符“？”，这A?是 . 的缩写(|A)。

我们想要定义一个转换 P，它接受任何正则表达式 A 并输出一个正则表达式 B=P(A)，它完全接受 A 接受的前缀。以下 P 的简单递归定义将做到这一点：

P(empty string) = empty string
P(c) = c?   if c is a literal character
P(A?) = P(A)
P(A*) = (A* P(A))
P(A B) = (P(A) | (A P(B)))
P(A|B) = (P(A) | P(B))

当然，正确性的证明是通过对正则表达式结构的归纳：观察它对于空字符串和文字字符是正确的，并且如果它对于Aand是正确的B，那么它对于A B, A|B, A*, and也是正确的A?。

我们还可以添加以下规则，这不是绝对必要的，但在文字字符串的常见情况下（即几个文字字符的连接）会导致更有效的输出表达式：

P(a B) = (a P(B))?  when a is a literal character

例子

考虑正则表达式/abc/。通常我们不指定或关心连接运算符是左结合还是右结合，因为结果接受的语言是相同的。但是，让我们以两种方式解决它。

如果我们将连接视为从左到右的关联：

P(/abc/) = P((a b) c)
         = P(a b) | ((a b) P(c))
         = P(a b) | ((a b) c?)
         = (a P(b))? | ((a b) c?)
         = (a b?)? | ((a b) c?)
         = /(ab?)?|abc?/

或者，如果我们将连接视为从右到左的关联，我们通过简单地重复应用规则获得更有效的（线性大小，不重复自身）输出：P(a B) = (a P(B))?

P(/abc/) = P(a (b c))
         = (a P(b c))?
         = (a (b P(c))?)?
         = (a (b c?)?)?
         = /(a(bc?)?)?/

Answer 3

取决于您所说的广义方式是什么意思。

\b(a(p?(p?(l?(e?)))))\b

编辑：加法背后的积极看法将代表一个更好的解决方案，但这完全取决于正则表达式机器的实现。