[katieChan]

Hola buen día!
Tengo que ver si las siguientes expresiones regulares son equivalentes

a) \[ \epsilon+(0+1)^*1 \] con \[ (0^*1)^* \]

b) \[ (0+1)^*1+0^* \] con \[ (1+0)(0^*1)^* \]

La primera parece ser cierta, pues notemos que el 1 es necesario, pero no logro encontrar la serie de igualdades para mostrarlo

Respecto a la segunda parecen ser que generan lenguajes diferentes

Alguien puede ayudarme? Gracias!

[Eren]

Modificado: Como explica martiniano, la respuesta que he dado para el inciso a) es incorrecta, y la he puesto en rojo para resaltar su incorrección.

Escribiendo $$(0^*1)^* = 1^* + (01)^* + (001)^* + (0001)^* + \cdots$$, vemos que $$011$$ no está en el lenguaje generado por $$(0^*1)^*$$, mientras que sí está en el de $$\epsilon + (0 + 1)^*1$$, pues este último contiene a cualquier cadena de ceros y unos siempre y cuando terminen en $$1$$.

Las expresiones regulares del inciso b) no son equivalentes. ¿Puedes encontrar una cadena reconocida por $$(0 + 1)^*1 + 0^*$$ pero no por $$(1 + 0)(0^*1)^*$$?

[martiniano]

Hola.

Hola buen día!
Tengo que ver si las siguientes expresiones regulares son equivalentes

a) \[ \epsilon+(0+1)^*1 \] con \[ (0^*1)^* \]

b) \[ (0+1)^*1+0^* \] con \[ (1+0)(0^*1)^* \]

La primera parece ser cierta, pues notemos que el 1 es necesario, pero no logro encontrar la serie de igualdades para mostrarlo

Respecto a la segunda parecen ser que generan lenguajes diferentes

Yo diría que tu intuición es buena. La primera es verdadera. Diría que ambas expresiones reconocen exactamente el lenguaje formado por la palabra vacía junto con todas las palabras que acaban en \[ 1 \]. Ahora bien, no sé cómo os hacen demostrar estas cosas. No sé a qué te refieres con lo de serie de igualdades. Tal vez te hayan dado una lista de propiedades a aplicar en estos casos o tal vez te refieras a probar la doble inclusión, u otra cosa... A lo mejor si me muestras algún ejemplo que tengas por ahí pueda ayudarte mejor.

La segunda es falsa. Como te dice Eren Echeverri intenta buscar un contraejemplo, es sencillo. Por si no lo encuentras te pongo uno en el spoiler.

Spoiler

La expresión de la derecha reconoce \[ 00 \], pero la de la izquierda no.

[cerrar]

Escribiendo $$(0^*1)^* = 1^* + (01)^* + (001)^* + (0001)^* + \cdots$$, vemos que $$011$$ no está en el lenguaje especificado por $$(0^*1)^*$$, mientras que sí está en el lenguaje de $$\epsilon + (0 + 1)^*1$$, pues esta última reconoce cualquier cadena de ceros y unos siempre y cuando terminen $$1$$.

Pues si no se me está escapando nada diría que \[ 011 \] sí que pertenece \[ (0^*1)^* \]. Observa que tanto \[ 01 \] como \[ 1 \] pertenecen a \[ 0^*1 \], luego la concatenación de ambas está en  \[ (0^*1)^* \].

Un saludo.

[Eren]

Pues si no se me está escapando nada diría que \[ 011 \] sí que pertenece \[ (0^*1)^* \]. Observa que tanto \[ 01 \] como \[ 1 \] pertenecen a \[ 0^*1 \], luego la concatenación de ambas está en  \[ (0^*1)^* \].

¿Qué tal, martiniano? Hace tiempo que no repaso esto de las expresiones regulares, y mi entender es que en $$(0^*1)^*$$ primero debes fijar la parte $$0^*1$$, y luego aplicar la estrella de Kleene a lo que obtengas, en lugar de simplemente concatenar las diferentes cadenas que puedas formar con $$0^*1$$. Si no es así, entonces necesito volver a estudiar este tema.

Saludos.

[martiniano]

Hola Eren Echeverri.

Yo diría que esto lo tienes confundido. Normalmente se define \[ L^k=\{w_1...w_k \textrm{ tal que }w_1,...,w_k\in{L}\} \] y \[ L^*=\cup_{k=0}^{\infty} {L^k} \]. De hecho, diría que la expresión que has dado a la derecha de esta igualdad no corresponde con un lenguaje regular:

Escribiendo $$(0^*1)^* = 1^* + (01)^* + (001)^* + (0001)^* + \cdots$$,

Fíjate en que para reconocer una palabra de ese lenguaje es necesario contar exactamente con cuántos ceros empieza, y el número de los mismos puede ser arbitrariamente alto. Esta tarea no se puede realizar con un autómata de estados finitos, ya que habría dos cadenas de ceros distintas que acabarían en un mismo estado.

Un saludo.

[Eren]

Hola, martiniano.

Sí que lo tenía bastante confundido, y tus explicaciones me aclaran bien la cuestión. Gracias por eso. He editado mi respuesta para hacer notar su incorrección.

Saludos.

[katieChan]

Ahora bien, no sé cómo os hacen demostrar estas cosas. No sé a qué te refieres con lo de serie de igualdades. Tal vez te hayan dado una lista de propiedades a aplicar en estos casos o tal vez te refieras a probar la doble inclusión, u otra cosa... A lo mejor si me muestras algún ejemplo que tengas por ahí pueda ayudarte mejor.

Hola martiniano, es a través de una lista de equivalencias, por ejemplo que sean \[ \alpha , \beta \] Expresiones regulares
Son asociativas y conmutan con \[ + \], también tenemos que
\[ \alpha \alpha ^* =  \alpha ^* \alpha, \alpha ^* = \alpha ^* \alpha ^*, \alpha ^* = \epsilon + \alpha \alpha ^* \]
o bien
\[ (\alpha + \beta)^* = (\alpha^* + \beta^*)^*, (\alpha + \beta)^* = (\alpha^* \beta^*)^* \]
Entre otras, aquí un ejemplo

Dadas dos expresiones regulares \[ R = bc + ac^*ac + ac^*c + a \] y \[ S = (b + ac^*a)c + ac^* \]
¿Generan el mismo lenguaje?

\[ R = bc + ac^*ac + ac^*c + a \]
\[ = (b + ac^*a)c + a(c^*c + \epsilon) \] por distribuitividad
\[  = (b + ac^*a)c + a(cc^* + ε)  \] propiedad anterior
\[  = (b + ac^*a)c + a(ε + cc^*) \] conmutatividad
\[ = (b + ac^*a)c + ac^* \] propiedad anterior
\[ = S \]
Así las ER son equivalentes

Ahí la cadena de igualdades

Gracias!

[martiniano]

Hola.

Pues la verdad es que yo tampoco veo la manera de hacerlo aplicando solamente estas leyes. No obstante, creo que te conviene conocer un teorema que tengo entre mis apuntes y que dice que no existe ningún conjunto finito de pares de expresiones regulares equivalentes que permita hallar la expresión regular más simple equivalente a una dada.

Yo interpreto que esto quiere decir que por muy larga que sea tu lista de propiedades siempre se podrá hallar una expresión regular que no pueda ser simplificada a otra equivalente mediante las propiedades de tu lista. Es por eso por lo que muchas veces se hace necesario recurrir a otros métodos para demostrar la equivalencia entre dos expresiones regulares.

Un saludo.