regex - 可空性(正则表达式)

Question

在 Brzozowski 的“正则表达式的导数”和其他地方，如果 R 可以为空，则函数 δ(R) 返回 λ，否则返回 ∅，包括以下子句:

δ(R1 + R2) = δ(R1) + δ(R2)
δ(R1 · R2) = δ(R1) ∧ δ(R2)

显然，如果 R1 和 R2 都可以为空，则 (R1 · R2) 可以为空，如果 R1 或 R2 可以为空，则 (R1 + R2) 可以为空。然而，我不清楚上述条款的含义。我的第一个想法是，将 (+)、(·) 或 bool 运算映射到常规集合是无意义的，因为在基本情况下，

δ(a) = ∅ (for all a ∈ Σ)
δ(λ) = λ
δ(∅) = ∅

并且 λ 不是集合(也不是集合 δ 的返回类型，它是一个正则表达式)。此外，此映射未指明，并且有单独的表示法。我理解可空性，但我对 δ 定义中的和、乘积和 bool 运算的定义迷失了:例如，在定义中，λ 或 ∅ 是如何从 δ(R1) ∧ δ(R2) 返回的关闭δ(R1·R2)？

Answer 1

我认为你是正确的映射 +和 ^到 bool 值 or和 and分别。看起来您引用的两行处理交替(总和)和串联(产品):

δ(R1 + R2) = δ(R1) + δ(R2)

R1的交替和 R2如果 R1 可以为空可以为空， R2可以为空，或者两者都可以为空 R1和 R2可以为空。

δ(R1 · R2) = δ(R1) ∧ δ(R2)

R1的串联和 R2只有在 R1 时才可以为空和 R2可以为空。

见 here对于这些规则的 Haskell 实现。