Expresiones regulares con caracteres repetidos

Necesito escribir una expresión regular que pueda detectar una cadena que contiene solo los caracteres x, y y z, pero donde los caracteres son diferentes de sus vecinos.

Aquí hay un ejemplo

xyzxzyz = Pase

xyxyxyx = Pase

xxyzxz = Fallido (repetido x)

zzzxxzz = Fail (se repiten los caracteres adyacentes)

Pensé que esto funcionaría ((x | y | z)?) *, Pero parece que no funciona. ¿Alguna sugerencia?

EDITAR

Tenga en cuenta que estoy buscando una respuesta que no permita mirar hacia adelante o mirar hacia atrás en las operaciones. Las únicas operaciones permitidas son alternancia, concatenación, agrupamiento y cierre

Por lo general, para este tipo de pregunta, si la expresión regular no es lo suficientemente simple como para derivarla directamente, puede comenzar dibujando un DFA y derivar una expresión regular a partir de ahí.

Debería poder derivar el siguiente DFA. q1, q2, q3, q4 son estados finales, y q1 también es el estado de inicio. q5 es el estado fallido / trampa.

DFA

Hay varios métodos para encontrar expresiones regulares para un DFA. Voy a usar el Método Algebraico de Brzozowski como se explica en la sección 5 de este documento :

Para cada estado qi, la ecuación Ri es una unión de términos: para una transición a de qi a qj, el término es aRj. Básicamente, observará todos los bordes salientes de un estado. Si Ri es un estado final, λ también es uno de los términos.

Permítanme citar las identidades de la sección de definición del artículo, ya que serán útiles más tarde (λ es la cadena vacía y ∅ es el conjunto vacío):

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

Como q5 es un estado de trampa, la fórmula terminará en una recursión infinita, por lo que puede soltarla en las ecuaciones. Va a terminar como un conjunto vacío y desaparecerá si lo incluye en la ecuación de todos modos (explicado en el apéndice).

Se te ocurrirá:

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

Resuelve la ecuación anterior con sustitución y el teorema de Arden, que dice:

Dada una ecuación de la forma X = AX + B donde λ ∉ A, la ecuación tiene la solución X = A*B

Llegarás a la respuesta.

No tengo tiempo y confianza para derivar todo, pero mostraré los primeros pasos de la derivación.

Elimine R4 por sustitución, tenga en cuenta que zλ se convierte en z debido a la identidad:

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

Reagruparlos:

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

Aplicar el teorema de Arden a R3:

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

Puede sustituir R3 de nuevo a R2 y R1 y eliminar R3. Dejo el rest como ejercicio. Continúa adelante y deberías llegar a la respuesta.

Apéndice

Explicaremos por qué los estados de trampas pueden descartarse de las ecuaciones, ya que simplemente desaparecerán de todos modos. Usemos el estado q5 en el DFA como ejemplo aquí.

 R5 = (x + y + z)R5 

Usa la identidad ∅ + x = x :

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

Aplicar el teorema de Arden a R5:

 R5 = (x + y + z)*∅ 

Usa la identidad ∅x = x∅ = ∅ :

 R5 = ∅ 

La identidad ∅x = x∅ = ∅ también tendrá efecto cuando R5 se sustituya en otras ecuaciones, haciendo que desaparezca el término con R5.

Esto debería hacer lo que quieras:

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

(Obviamente, solo en motores con anticipación)

El contenido en sí es manejado por la segunda parte: [xyz]* (cualquier número de caracteres x, y, o z). Las anclas ^...$ están aquí para decir que tiene que ser la totalidad de la cadena. Y la condición especial (sin pares adyacentes) es manejada por un lookahead negativo (?!.*(.)\1) , que dice que no debe haber un personaje seguido del mismo personaje en ninguna parte de la cadena.

He tenido una idea mientras estaba caminando hoy y la he puesto en modo regex y todavía tengo que encontrar un patrón que no coincida correctamente. Así que aquí está la expresión regular:

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

¡Aquí hay un violín que lo acompaña!

Si encuentra una discrepancia en el patrón, dígame que intentaré modificarlo. Sé que es un poco tarde, pero realmente me molestó el hecho de que no pude resolverlo.

    Intereting Posts