[2019] [Julio] [Ejercicio 1] [Parte c] Inclusión de lenguajes regulares

[2019] [Julio] [Ejercicio 1] [Parte c] Inclusión de lenguajes regulares

de Santiago Cuadrado Vilar -
Número de respuestas: 2

Buenas, haciendo el examen de Julio de 2019, en el ejercicio 1 esta la siguiente parte:

Y me surgió la duda, dado que los x de Lc cumplen que pertenecen a Lc1, eso quiere decir que Lc está incluido en Lc1 verdad? Entonces, si Lc1 es regular, Lc también lo es por inclusión?
En otras palabras mi duda es si un lenguaje está dentro de un lenguaje regular, también lo es?
Esto se cumple en otros niveles de la jerarquía? Hablando de LLC y LRE. Y si es así, se puede asumir esto en un examen o es necesaria una demostración?

Muchas gracias, Santiago.


En respuesta a Santiago Cuadrado Vilar

Re: Inclusión de lenguajes regulares

de Santiago Cuadrado Vilar -
Pensando un poco mi pregunta me di cuenta que esa afirmación es falsa, ya que, por ejemplo si tomo L={a^nb^n, con n >0}, tengo que L está incluido en sigma aster que es regular y L no lo es. Disculpen las molestias.
En respuesta a Santiago Cuadrado Vilar

Re: Inclusión de lenguajes regulares

de Diego Garat -
hola:

exactamente. se suele confundir la jerarquía de chomsky (inclusión en conjuntos de conjuntos de tiras) con la inclusión de lenguajes (conjuntos de tiras). pero como bien decís, y para llevarlo a un extremo, todos conjunto ---sin importar su tipo--- está incluido en un lenguaje regular (sigma*) y todo lenguaje ---sin importar su tipo--- incluye a un lenguaje regular (el vacío).

saludos,
d.-