TeoLeng: Demostración de propiedades de lenguajes usando teoría de conjuntos

Buenas, he visto varias soluciones de parciales sobre propiedades de los lenguajes y se resuelven usando conceptos enfocados en que pasa con cada lenguaje puntual.

En varios de ellos he llegado a la misma solución solo aplicando la Jerarquía de Chomsky y teoría de conjuntos.

Visto que no he visto soluciones con el último método mencionado, se toma bien una solución de esa forma o esperan que, además de eso, se utilice alguna propiedad sobre el lenguaje en cuestión?

Espero se haya entendido la duda.

Desde ya, muchas gracias!

Re: Demostración de propiedades de lenguajes usando teoría de conjuntos

de Diego Garat - lunes, 26 de junio de 2017, 10:13

hola:

no entiendo la pregunta. ¿tenés algún ejemplo de lo que planteás?

saludos,

d.-

Re: Demostración de propiedades de lenguajes usando teoría de conjuntos

de Hugo Sebastian Rodriguez Reyes - lunes, 26 de junio de 2017, 17:02

Por ejemplo en el segundo parcial del 2016, L1 es regular y L2 es libre de contexto no regular.

Una pregunta dice que L2-L1 es recursivamente enumerable.

En la demostración aplican varias propiedades, pero yo lo hice viendo la Jerarquía de Chomsky y la definición de diferencia de conjuntos.

Esa diferencia me da un libre de contexto no regular y por la Jerarquía de Chomsky, los libres de contextos están contenidos en los recursivamente enumerables, ergo, L2-L1 es recursivamente enumerable.

Espero haya quedado claro con el ejemplo la duda planteada.

Re: Demostración de propiedades de lenguajes usando teoría de conjuntos

de Diego Garat - lunes, 26 de junio de 2017, 22:14

hola:

¿y qué podías afirmar de L2-L1 según la jerarquía de chomsky? la jerarquía habla de conjuntos de lenguajes, no de lenguajes. L2-L1 no te da un anillo de la jerarquía de chomsky, sino otro lenguaje que, en principio, podría residir en cualquier anillo, porque dada la definición genérica no sabés cómo son las tiras de ese lenguaje resultante.

saludos,

d.-