Expressões regulares com caracteres repetidos

Eu preciso escrever uma expressão regular que possa detectar uma string que contenha apenas os caracteres x, ye z, mas onde os caracteres são diferentes de seus vizinhos.

Aqui está um exemplo

xyzxzyz = Passe

xyxyxyx = passar

xxyzxz = falha (repetido x)

zzzxxzz = Fail (caracteres adjacentes são repetidos)

Eu pensei que isso funcionaria ((x | y | z)?) *, Mas parece não funcionar. Alguma sugestão?

EDITAR

Por favor note, estou procurando uma resposta que não permite olhar para frente ou olhar para trás as operações. As únicas operações permitidas são alternação, concatenação, agrupamento e fechamento

Geralmente, para esse tipo de pergunta, se a regex não for simples o suficiente para ser derivada diretamente, você pode começar a desenhar um DFA e obter uma regex a partir daí.

Você deve conseguir derivar o seguinte DFA. q1, q2, q3, q4 são estados finais, com q1 sendo também o estado inicial. q5 é o estado de falha / trap.

DFA

Existem vários methods para encontrar a expressão regular para um DFA. Eu vou usar o método algébrico Brzozowski como explicado na seção 5 deste artigo :

Para cada estado qi, a equação Ri é uma união de termos: para uma transição a de qi para qj, o termo é aRj. Basicamente, você verá todas as bordas de saída de um estado. Se Ri é um estado final, λ é também um dos termos.

Deixe-me citar as identidades da seção de definição do artigo, pois elas serão úteis mais tarde (λ é a string vazia e ∅ é o conjunto vazio):

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

Como q5 é um estado de interceptação, a fórmula terminará em uma recursion infinita, para que você possa soltá-la nas equações. Ele terminará como um conjunto vazio e desaparecerá se você incluí-lo na equação de qualquer maneira (explicado no apêndice).

Você vai chegar com:

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

Resolva a equação acima com substituição e o teorema de Arden, que afirma:

Dada uma equação da forma X = AX + B onde λ ∉ A, a equação tem a solução X = A*B

Você chegará à resposta.

Eu não tenho tempo e confiança para derivar a coisa toda, mas mostrarei os primeiros passos da derivação.

Remova R4 por substituição, observe que zλ se torna z devido à identidade:

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

Reagrupe-os:

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

Aplique o teorema de Arden ao R3:

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

Você pode replace R3 de volta para R2 e R1 e remover R3. Deixo o resto como exercício. Continue em frente e você deve alcançar a resposta.

Apêndice

Vamos explicar por que os estados de armadilhas podem ser descartados das equações, já que eles simplesmente desaparecerão de qualquer maneira. Vamos usar o estado q5 no DFA como exemplo aqui.

 R5 = (x + y + z)R5 

Use identidade ∅ + x = x :

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

Aplique o teorema de Arden ao R5:

 R5 = (x + y + z)*∅ 

Use identidade ∅x = x∅ = ∅ :

 R5 = ∅ 

A identidade ∅x = x∅ = ∅ também terá efeito quando R5 for substituído em outras equações, fazendo com que o termo com R5 desapareça.

Isso deve fazer o que você quer:

 ^(?!.*(.)\1)[xyz]*$ 

(Obviamente, apenas em motores com lookahead)

O conteúdo em si é tratado pela segunda parte: [xyz]* (qualquer número de caracteres x, y ou z). As âncoras estão aqui para dizer que tem que ser a totalidade da corda. E a condição especial (sem pares adjacentes) é manipulada por um lookahead negativo (?!.*(.)\1) , que diz que não deve haver um caractere seguido pelo mesmo caractere em qualquer lugar da string.

Eu tive uma idéia enquanto eu estava andando hoje e coloquei na regex e ainda não encontrei um padrão que não corresponde corretamente. Então aqui está o regex:

 ^((y|z)|((yz)*y?|(zy)*z?))?(xy|xz|(xyz(yz|yx|yxz)*y?)|(xzy(zy|zx|zxy)*z?))*x?$ 

Aqui está um violino para acompanhá-lo!

Se você encontrar uma incompatibilidade de padrões, diga-me que tentarei modificá-lo! Eu sei que é um pouco tarde, mas fiquei realmente incomodado com o fato de que não consegui resolver.