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

Question

Estoy trabajando en mi tarea para mi clase de compilador y tengo el siguiente problema:

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

Después de mucho trabajo de pizarra, se 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 esto lo más simplificado que puedo obtener? He considerado construir el DFA tratando de minimizar la cantidad de estados allí para ver si me ayudaría a simplificar, pero pensé que primero pediría a los gurús de expresiones regulares en SO.

Answer 1

Tome la recomendación de Greg D de comenzar con un (aa) * y continuar desde allí. Sepp2k casi tiene razón, pero la verdadera consideración es que no te importa la otra carta. Lo que quiero decir es, cuando estás mirando el "número impar de a" restricción, no le importa en absoluto qué b están en su cadena. Por lo tanto, pegue b * 's en cualquier lugar que pueda :)

La respuesta de Sepp2k es casi correcta, pero esta es correcta:

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

Para elaborar, esta expresión regular calcula todas las cadenas con un número impar de a (primera sección), y las cadenas OR con cualquier cadena que contenga un número impar de b.

Answer 2

Esto debería funcionar:

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

Answer 3

Me temo que no creo que su expresión regular tal como está escrita sea correcta. Considere la cadena:

aba

Tenemos un par de opciones para los partidos, pero el hecho de que sea de longitud impar significa que debemos hacer coincidir un solitario a en el frente, entonces:

(a)(ba)

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

Al tratar con una restricción como esta, me resultó más fácil comenzar desde la restricción central e ir desde allí. En este caso, su restricción es `` impar ''. así que comienza con

a(aa)*

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

Answer 4

Creo que debe abordar el problema de manera diferente.

Está intentando hacer coincidir cualquier cosa que no tenga números pares de a y b .

Probablemente sería más fácil comenzar con algo que coincida con los números pares de a y b . Todo lo que tiene que hacer en ese momento es agregar algo en el extremo que coincida con la cadena más pequeña que realmente desea que coincida.