regex - 具有重复字符的正则表达式

Question

我需要编写一个正则表达式来检测仅包含字符 x、y 和 z 的字符串，但这些字符与其相邻字符不同。

举个例子

xyzxzyz = 通过

xyxyxyx = 通过

xxyzxz = 失败(重复 x)

zzzxxzz = 失败(相邻字符重复)

我认为这会起作用 ((x|y|z)?)*，但它似乎不起作用。有什么建议吗？

编辑

请注意，我正在寻找不允许前瞻或后视操作的答案。唯一允许的操作是交替、串联、分组和闭合

Answer 1

通常这类题，如果regex不够简单，不能直接推导，可以从画DFA开始，推导regex。

您应该能够推导出以下 DFA。 q1、q2、q3、q4 是结束状态，q1 也是起始状态。 q5 是失败/陷阱状态。

有几种方法可以找到 DFA 的正则表达式。我将使用 Brzozowski 代数方法，如 this paper 的第 5 节中所述。 :

对于每个状态 qi，方程 Ri 是项的并集:对于从 qi 到 qj 的转换 a，项是 aRj。基本上，您将查看一个状态的所有传出边。如果 Ri 是最终状态，则 λ 也是其中一项。

让我引用论文定义部分的恒等式，因为它们稍后会派上用场(λ 是空字符串，∅ 是空集):

(ab)c = a(bc) = abc
λx = xλ = x
∅x = x∅ = ∅
∅ + x = x
λ + x* = x*
(λ + x)* = x*

由于 q5 是陷阱态，公式将以无限递归结束，因此您可以将其放入方程中。如果您无论如何将它包含在等式中，它将最终成为空集并消失(在附录中解释)。

你会想出:

R1 = xR2 + yR3 + zR4 + λ
R2 =     + yR3 + zR4 + λ
R3 = xR2 +     + zR4 + λ
R4 = xR2 + yR3       + λ

用代入法和 Arden 定理求解上述方程，该定理指出:

Given an equation of the form X = AX + B where λ ∉ A, the equation has the solution X = A*B.

你会得到答案。

我没有时间和信心推导整个事情，但我会展示推导的前几个步骤。

通过替换删除 R4，注意 zλ 由于身份而变成 z:

R1 = xR2 + yR3 + (zxR2 + zyR3 + z) + λ
R2 =     + yR3 + (zxR2 + zyR3 + z) + λ
R3 = xR2 +     + (zxR2 + zyR3 + z) + λ

重组他们:

R1 = (x + zx)R2 + (y + zy)R3 + z + λ
R2 =       zxR2 + (y + zy)R3 + z + λ
R3 = (x + zx)R2 +       zyR3 + z + λ

将 Arden 定理应用于 R3:

R3 = (zy)*((x + zx)R2 + z + λ)
   = (zy)*(x + zx)R2 + (zy)*z + (zy)*

您可以将 R3 替换回 R2 和 R1 并删除 R3。我把剩下的留作练习。继续前进，您应该找到答案。

附录

我们将解释为什么陷阱态可以从方程中丢弃，因为它们无论如何都会消失。这里以DFA中的状态q5为例。

R5 = (x + y + z)R5

使用恒等式∅ + x = x:

R5 = (x + y + z)R5 + ∅

将 Arden 定理应用于 R5:

R5 = (x + y + z)*∅

使用恒等式∅x = x∅ = ∅:

R5 = ∅

恒等式∅x = x∅ = ∅也会在R5代入其他方程时生效，导致带R5的项消失。