¿Es posible simplificar esta expresión regular más?

estoy trabajando en algunas tareas para mi clase compilador y tengo el siguiente problema:¿Es posible simplificar esta expresión regular más?

Escribir una expresión regular para todas las cadenas de un 's y b' s que contienen un número impar de un o un número impar de b 's (o ambos).

Después de mucho trabajo pizarra me ocurrió la siguiente solución:

(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*

sin embargo, es que este es el más simplificada que puedo conseguirlo? Consideré construir el DFA tratando de minimizar el número de estados para ver si eso me ayudaría a simplificar, pero pensé que primero debería preguntarle a los gurús de regex en SO.

Fuente

2009-09-16 Anonymous

¿Qué características avanzadas de regex tiene permitido usar? –

está usando expresiones regulares en Computer Science, no PCRE o posix regex;) Son diferentes. –

@Brad Gilbert, supongo que solo podemos usar la expresión regular que se ha introducido hasta ahora en el libro, que no es mucho. (*, +,?, |, [], ^). Bastante simple –

Take Greg D's recomendación de comenzar con un (bis) *, e ir desde allí. Sepp2k casi tiene razón, pero la verdadera consideración es que no te importa la otra letra. Lo que quiero decir es que cuando miras la restricción del "número impar de a", no te importa en absoluto qué b están en tu cadena. Por lo tanto, palo de b * 's en cualquier lugar que puede :)

respuesta de Sepp2k es casi correcta, pero éste es correcta:

b* a b* (a b* a b*)* | a* b a* (b a* b a*)*

Elaborar, esta expresión regular se da cuenta de todas las cadenas con un número impar de unos de (primera sección), y OR es aquellas cadenas con cualquier cadena que contiene un número impar de b.

Fuente

2009-09-16 20:00:22

@Walt W, estoy ejecutando este a través de sus pasos, pero creo que estás en lo cierto. – mmcdole

por favor dígame la expresión regular para cualquier cadena que contenga un número par de a's e incluso número de b's –

¿Quiere decir un número par de a O un número par de b? Supongo que podrías hacer un AND con lookaheads de longitud cero ... Sin embargo, eso no es estándar en expresiones regulares. Si desea cambiar esta ecuación de impar a par, simplemente suelte los dos primeros términos de cada segmento (b * a desde el lado izquierdo y a * b desde el lado derecho) –

Me temo que no creo que su expresión regular sea correcta. Considere la cadena:

aba

Tenemos un par de opciones para los partidos, pero el hecho de que es raro de longitud significa que debe coincidir con un un solitario en la parte delantera, por lo que:

(a)(ba)

Pero, lamentablemente , es imposible que su segunda agrupación principal coincida (ba).

Cuando se trata de una restricción como esta, me resultó más fácil comenzar desde la restricción del núcleo e ir desde allí. En este caso, su limitación es "raro", así que empieza con

a(aa)*

para forzar un número impar de a 's e ir de allí. :)

Fuente

2009-09-16 19:38:42

@Greg D, eso es cierto. Déjame pensarlo por un segundo. – mmcdole

Esto debería funcionar:

b* a b* (a b* a b*)* | a* b a* (b a* b a*)*

Fuente

2009-09-16 19:50:44 sepp2k

Estaba escribiendo algo similar :) Para elaborar, esta expresión regular descifra todas las cadenas con un número impar de a (primera sección), y OR las cadenas con cualquier cadena que contenga un número impar de b. Sin embargo, aquí hay un pequeño error, ya que el primer término necesita b * al final, y la segunda opción necesita un * al final. De lo contrario, abbba no será aceptado. –

@ sepp2k, esto funciona en todos mis casos de prueba. ¿Puedes describir tu proceso de pensamiento cuando lo estabas haciendo? Es mucho más simple que el camino que estaba bajando. – mmcdole

Nadie dijo que no puede ser ambiguo. Walt tiene razón, no está terminado, pero todos los bits importantes están ahí. :) –

Creo que debe abordar el problema de manera diferente.

Usted está tratando de hacer coincidir cualquier cosa que no tenga números pares tanto de a como de b.

Probablemente sería más fácil comenzar con algo que coincide incluso número de a y b. Todo lo que tienes que hacer en ese punto sería agregar algo en el extremo que coincida con la cadena más pequeña que realmente quieras unir.

Fuente

2009-09-16 20:10:17

¿Es posible simplificar esta expresión regular más?

Respuesta

Cuestiones relacionadas