Simplifique esta expresión regular

Estoy haciendo algunos ejercicios de examen previo para mi clase de compiladores, y necesitaba simplificar esta expresión regular.Simplifique esta expresión regular

(a U b)*(a U e)b* U (a U b)*(b U e)a*

Evidentemente, la e es la cadena vacía, y la U significa unión.

Hasta ahora, creo que uno de los (a U b) * se puede eliminar, como la unión de un U a = a. Sin embargo, no puedo encontrar ninguna otra simplificación, y no estoy tan bien con los otros problemas hasta el momento. :(

Cualquier ayuda se agradece, gracias mucho!

Fuente

2011-02-10 CompilersBeginner

Preferiría mucho las explicaciones a cualquier respuesta, o incluso sugerencias en lugar de respuestas, estoy haciendo ejercicios de preevaluación, ¡las respuestas sin explicaciones no me ayudarán mucho! ¡Gracias! – CompilersBeginner

Creo que mi respuesta aceptada es incorrecta, como se señala en los comentarios. Creo que el resultado es (a U b) * pero mi explicación no es correcta. – Piva

poco oxidado en expresiones regulares, pero si todavía * representa el "cero o más ocurrencias" puede reemplazar:

(a U e)b* for (a U b)*

que sale de la primera parte con:

(a U b)*(a U b)* = (a U b)*

En el lado derecho, usted tiene que

(b U e)a* = (b U a)*

Ahora, ya que un T b = b U una, se obtiene:

(a U b)*(a U b)*

en el lado derecho, lo que deja solo

(a U b)* U (a U b)* = (a U b)*

Creo que eso es todo ...

Fuente

2011-02-10 01:59:58 Piva

Dios mío, me duele la cabeza porque mi expresión regular también está oxidada. Podrías tener razón, pero * ¿qué pasó con la 'e' token *? No veo cómo se elimina. Pero es posible que no lo vea (de nuevo, la edad y la falta de café se combinan con la oxidación de la expresión regular). –

El primer paso es incorrecto, ya que el anterior solo permite 1 'a' y solo en la primera posición. –

@BoltClock: No hay 'a?' En la respuesta que veo. –

creo que todo esto es equivalente a (a U b)* (o en la mayoría de las gramáticas de expresiones regulares, (a|b)*)

Fuente

2011-02-10 01:56:01

Como estoy haciendo problemas de práctica para un examen, estoy mucho más interesado en cómo llegaste a esta conclusión. ¿Podrías compartir eso? – CompilersBeginner

Aquí está mi razonamiento: mire la rama izquierda de la unión superior. Primero, tome '(a U b) * (a U e)'; distribuya la concatenación a través de la unión para obtener '(a U b) * a U (a U b) *'. La segunda parte es un superconjunto de la primera, por lo que se colapsa en '(a U b) *'. Agregar el 'b *' al final hace lo mismo: cualquier cosa que coincida con '(a U b) * b *' también será igualada por '(a U b) *' y viceversa. Eso convierte al RE en '(a U b) * U (a U b) * (b U e) a *'; dado que el lado derecho solo puede aceptar cadenas de 'a' y' b', es un subconjunto del lado izquierdo, por lo que la RE simplifica simplemente '(a U b) *'. –

@CompilersBeginner: dos formas son equivalentes si el hecho de que coincida con el primero implica que coincida con el segundo, y que coincida con el segundo implica que coincida con el primero, ¿no? Tu expresión nunca introduce ningún token excepto 'a' y' b', por lo que cualquier cosa que coincida con él también coincide con '(a U b) *'. Y cualquier '(a U b) *' coincide con el suyo tomando la primera rama, '(a U b) * (a U e) b *', y luego eligiendo la rama de cadena vacía '(a U b) * eb * ', y finalmente elegir la repetición cuenta 0 para' b * '. –

Primera tran pizarra a una descripción Inglés de la lengua:

(a U b)*(a U e)b* U (a U b)*(b U e)a*

Traduce a:

Cualquier secuencia de a s o b s, seguido por una opcional a, seguido de cualquier número de b s .

Cualquier número de a s y b s, seguido de un opcional b, follwed por cualquier número de a s

Hay una gran cantidad de solapamiento aquí - al menos (a U b)*(a U e) es exactamente igual que (a U b)*, porque "Cualquier secuencia de a sy b s" necesariamente termina con a o épsilon (como cualquier cadena puede terminar con epsilon) así que esos grupos pueden ser eliminados, dejando

(a U b)*b* U (a U b)*a*

se traduce en:

Cualquier secuencia de a s o b s, seguido de cualquier número de b s .

Cualquier número de a s y b s, follwed por cualquier número de a s

Ahora la primera sección de aquellos a los grupos más exteriores es el mismo, por lo que permite colapsar, aquellos en los uno

(a U b)*(a* U b*)

se traduce en:

Cualquier secuencia de a s o b s, seguido de cualquier número de a s o por cualquier número b s.

ahora espera un minuto "cualquier secuencia de A y B" necesariamente termina con "cualquier secuencia de a s o cualquier secuencia de b s", lo que significa cualquier cosa que coincide con la primera parte puede coincidir toda la expresión regular (porque la segunda parte puede tener una longitud de cero) así que ¿por qué no nos hacen

(a U b)*

TA DA. Sencillo.

Fuente

2011-02-10 02:01:18 tobyodavies

Según su razonamiento (a U b) * b se reduciría de la misma manera ... pero no es así. Debe asegurarse de que no solo todas las coincidencias continúen coincidiendo, sino que todas las entradas rechazadas sigan siendo rechazadas y su argumento omita la última. –

@Ben ¿Qué paso pierde información? Muchas de las simplificaciones se basan en que todos los bits finales pueden tener 0 de longitud, lo que no ocurre con su ejemplo, por lo que no estoy seguro de a qué se refiere. – tobyodavies

@Ben, creo que te estás refiriendo a mi 1er o 3er paso cuando digo que debido a que la 1ra repetición _necesariamente_ termina con la segunda, podemos eliminar la segunda, que nuevamente no se aplica a tu ejemplo - '(a U b)' no necesariamente termina con una 'b'; podría terminar en' a', por lo que la simplificación no se aplica. – tobyodavies

Te voy a dar una idea de cómo iba a resolverlo: (no muy formal y sin garantía)

mirar el lado izquierdo de la T principal:

(U b) * - ¿Qué significa eso? Una combinación de a's y b's de longitud n, donde n> = 0.

Siguiente viene (a U e). ¿Qué tenemos aquí? Una palabra a o vacía. Si quisiéramos eso, podríamos haberlo obtenido ya en la parte anterior. Si queremos el e, bueno podemos dejarlo fuera de todos modos. Tenga en cuenta que no tenemos que tomar una a porque tenemos la opción de elegir e. Así que podemos omitir esta parte entera.

¿Qué sigue? segundo*. ¿Que es eso? Tantos b's como queramos ¡Podríamos haber conseguido esos en la primera parte también! podemos dejar eso fuera!

Por lo tanto, lo único a la izquierda es (a U b) *.

Vamos a echar un vistazo en el lado derecho:

Muy bien, este es muy fácil ahora, podemos utilizar la misma idea es sólo letras diferentes.

También obtendremos (a U b) * de la misma manera.

Así que al final tenemos (a U b) * U (a U b) * que usted sabe que es igual a (a U b) *.

Fuente

2011-02-10 02:06:31 FabianB

Por su razonamiento '(a U b) * b' se reduciría de la misma manera ... pero no es así. –

Gracias por la sugerencia, estaba tratando de dar un enfoque menos formal en mi respuesta. No estoy seguro de cómo mejorar la respuesta sin renunciar a eso. – FabianB

Simplifique esta expresión regular

Respuesta

Cuestiones relacionadas