具有重复字符的正则expression式
我需要编写一个正则expression式，它可以检测到只包含字符x，y和z的string，但字符与邻居不同。
这是一个例子
xyzxzyz =通过
xyxyxyx =通过
xxyzxz =失败（重复x）
zzzxxzz =失败（相邻的字符重复）
我以为这会工作（（x | y | z）？）*，但它似乎不工作。 有什么build议么？
编辑
请注意，我正在寻找一个答案，不允许向前看或后面的操作。 允许的唯一操作是交替，连接，分组和closures
通常对于这种types的问题，如果正则expression式不够直接导出，那么可以从绘制DFA开始，从那里派生一个正则expression式。
您应该能够派生出以下DFA。 q1，q2，q3，q4是结束状态，q1也是开始状态。 q5是失败/陷阱状态。
有几种方法可以findDFA的正则expression式。 我将使用Brzozowski代数方法，如本文第5节所述：
对于每个状态qi，方程Ri是项的并集：对于从qi到qj的转换a ，项是aRj。 基本上，你会看到一个状态的所有传出边缘。 如果Ri是最终状态，则λ也是其中的一个项。
让我引用文章定义部分的标识，因为它们稍后会派上用场（λ是空string，∅是空集）：
(ab)c = a(bc) = abc λx = xλ = x ∅x = x∅ = ∅ ∅ + x = x λ + x* = x* (λ + x)* = x*
由于q5是一个陷阱状态，所以这个公式将会结束一个无限recursion，所以你可以把它放在方程中。 如果将它包含在方程中（如附录所述），它将以空集的forms结束并消失。
你会想出：
R1 = xR2 + yR3 + zR4 + λ R2 = + yR3 + zR4 + λ R3 = xR2 + + zR4 + λ R4 = xR2 + yR3 + λ
用替代和Arden定理求解上面的方程，其中说：
给定一个forms为
X = AX + B的方程，其中λ∉A，该方程有解X = A*B
你会得到答案。
我没有时间和信心来推导整个事情，但是我会展示推导的前几个步骤。
通过replace去除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 + λ
将阿登定理应用于R3：
R3 = (zy)*((x + zx)R2 + z + λ) = (zy)*(x + zx)R2 + (zy)*z + (zy)*
您可以将R3replace回R2和R1并删除R3。 我把其余的作为练习。 继续前进，你应该得到答案。
附录
我们将解释为什么陷阱状态可以从方程中抛弃，因为它们将会消失。 让我们以DFA中的状态q5为例。
R5 = (x + y + z)R5
使用身份∅ + x = x ：
R5 = (x + y + z)R5 + ∅
将阿登定理应用于R5：
R5 = (x + y + z)*∅
使用身份∅x = x∅ = ∅ ：
R5 = ∅
当R5代入其它方程时，身份∅x = x∅ = ∅也会生效，导致R5的项消失。
这应该做你想要的：
^(?!.*(.)\1)[xyz]*$
（很显然，只有带有前视的引擎）
内容本身由第二部分处理： [xyz]* （任意数量的x，y或z字符）。 主播^...$在这里说，它必须是整个string。 而且特殊的条件（没有相邻的对）是由负向前瞻(?!.*(.)\1) ，它表示在string中任何地方都不能有一个字符后面跟着相同的字符。
当我今天走路时，我有一个想法，把它放在正则expression式，我还没有find一个模式，它不正确。 所以这里是正则expression式：
^((y|z)|((yz)*y?|(zy)*z?))?(xy|xz|(xyz(yz|yx|yxz)*y?)|(xzy(zy|zx|zxy)*z?))*x?$
这是一个小提琴去吧！
如果你发现模式不匹配告诉我，我会尝试修改它！ 我知道这有点晚了，但我真的很困扰，我无法解决这个问题。
