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

Question

我需要编写一个正则表达式,它可以检测只包含字符x,y和z的字符串,但字符与其邻居不同.

这是一个例子

xyzxzyz =通行证

xyxyxyx =通过

xxyzxz =失败(重复x)

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

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

编辑

请注意,我正在寻找一个不允许向前看或看后面操作的答案.允许的唯一操作是交替,连接,分组和关闭

Answer 1

通常对于这种类型的问题,如果正则表达式不够简单直接派生,您可以从绘制DFA开始并从那里派生正则表达式.

您应该能够派生以下DFA.q1,q2,q3,q4是结束状态,q1也是起始状态.q5是失败/陷阱状态.

有几种方法可以为DFA查找正则表达式.我将使用Brzozowski代数方法,如本文第5部分所述:

对于每个状态qi,等式Ri是项的并集:对于a从qi到qj 的转换,该项是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定理求解上面的等式,其中说明:

给定一个形式的公式,X = AX + B其中λ∉A,方程有解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的项消失.