Manejo de expresiones regulares

Manejo de expresiones regulares

de Valentina Pereira Ciaffone -
Número de respuestas: 1

Hola! 

Se me esta complicando el manejo de las expresiones regulares para hacer pruebas del tipo L(r1) ⊆ L(r2)  con r1 y r2 expresiones regulares.

Lei la prueba que subieron, pero para x ∈ L(ab)* es fácil ver que existe k tal que x = (ab)^k pero en el caso de expresiones regulares mas complejas como r1 = b.(a.b |b)* como se procede? vamos utilizando la def de L y separando el lenguaje en L(r1) = L(b) ∪ L(a.b|b)*.

En caso de aparecer mas de un exponente para representar una tira, sobre que se haría la inducción completa?

Dejo esta pregunta, porque es lo que mas me ha trancado al hacer ejercicios como el 4 o  el 5. La intuición de por que representarían el mismo lenguaje la tengo, el problema es plasmarlo en la prueba. 

 

En respuesta a Valentina Pereira Ciaffone

Re: Manejo de expresiones regulares

de Santiago Gongora -
Buen día Valentina,

quizás te sirva ver posts como estos:

En lo siguiente voy a considerar que se quiere probar algo del estilo r=s donde tanto r como s son expresiones regulares que generan a L(r) y L(s) respectivamente.

La idea que nosotros les damos es que esas igualdades "más complicadas", como vos decís, se pueden probar usando tiras genéricas w que pertenezcan al lenguaje de origen L(r). Esas tiras genéricas se pueden "desmenuzar" en subtiras donde cada una de ellas va a pertenecer al lenguaje generado por alguna expresión regular. Ahí utilizando la definición inductiva de Expresión Regular (que asocia los operadores de ER con conjuntos de tiras), la definición de Clausura de Kleene y operadores y propiedades de Teoría de Conjuntos, vas a poder llegar a una expresión para esa tira genérica w que pueda ser generada por s o, en otras palabras, que pertenezca a L(s).

A las órdenes por cualquier cosa,
Santi