TeoLeng: [Ejercicio 5] [Parte 2]

Hola, tenía una consulta acerca del ejercicio 5.

Cuando queremos probar que dos expresiones son iguales es ver que definen el mismo lenguaje, esto es correcto? Porque lo piden en la parte 2 del ej5.

Otra consulta respecto a esto, es lo mismo poner que x pertenece a una expresión regular y poner que x pertenece a lenguaje de esa expresión regular? O esta mal decir que x pertenece a una expresión regular?

Es decir,

x ∈ ab* y x ∈ L(ab*)

Re: [Ejercicio 5] [Parte 2]

de Santiago Gongora - lunes, 13 de marzo de 2023, 12:17

Buen día Mariana,

arranco primero por tu segunda pregunta. Es incorrecto decir que

$x \in ab^*$ . Lo que queremos decir es "la tira x pertenece al conjunto de tiras generado por la expresión regular

$ab^*$ ". Para decir lo de "el conjunto generado por la expresión regular r" tenemos la notación "L(r)" así que siempre debemos decir:

$x \in L(ab^*)$ .

Sobre la primera pregunta es así como decís: probar que dos expresiones regulares son equivalentes es probar que generan el mismo lenguaje. O sea, que si r y s son expresiones regulares, r=s implica que L(r)=L(s). De hecho, ese es el espíritu del ejercicio 6 íntegramente, probar esas "identidades" requiere probar que los lenguajes generados por ambas expresiones es el mismo. Recordá que está este documento para guiarte en esas pruebas y este video donde lo leemos.

Una prueba r=s típicamente se hace así, por doble inclusión:

Primero probamos que $\forall w \in L(r) \Longrightarrow w \in L(s)$
Luego probamos que $\forall w' \in L(s) \Longrightarrow w' \in L(r)$

Cualquier cosa volvé a preguntar porfa.

Saludos,
Santi