[2022] [Julio] [Ejercicio 1] [Parte b]

[2022] [Julio] [Ejercicio 1] [Parte b]

de Enrique Galasso Gonzalez -
Número de respuestas: 3

El ejercicio plantea:

Si L1 ∩ L2 es regular, L1 ∩ L3 es libre de contexto no regular y L1 ≠ L2, entonces L1 ∩ L2 ∩ L3 es regular.

En la solución se plantea:

Sean L1=Σ* (Σ={a,b}), L2=L(a*b*), L3={ak bk / k≥0}. Se tiene entonces que L1 ∩ L2 ∩ L3 = L3 que no es regular 

Se entiende de la solución que {a*b*} ∩ {ak bk / k≥0} = {ak bk / k≥0}

Mi duda es: ¿ {ak bk / k≥0} ⊂ {a*b*} ?


En respuesta a Enrique Galasso Gonzalez

Re: Examen – Julio de 2022 (Ejercicio 1 - Parte b)

de Diego Garat -
hola:

sea x una tira de {a^k b^k / k≥0}, luego existe M tal que x = a^M b^M

por la definición de clausura de kleene:
a^M pert L(a*)
b^M pert L(b*) luego (por def. de concatenación) a^M.b^M pert L(a*).L(b*). = L(a*.b*)

entonces si x pert {ak bk / k≥0} => x pert L(a*.b*) y se prueba la inclusión. además, la tira bbb pertenece a L(a*.b*) pero no a {ak bk / k≥0}. luego, la inclusión es estricta.


en otras palabras, una tira de la forma a^k b^k no deja de ser una secuencia de letras a seguida por una secuencia de letras b, y por lo tanto pertenece a L(a*b*)

saludos,
d.-
En respuesta a Diego Garat

Re: Examen – Julio de 2022 (Ejercicio 1 - Parte b)

de Enrique Galasso Gonzalez -
De acuerdo, en realidad mi confusión se debe a interpretar que al cumplirse {ak bk / k≥0} ⊂ {a*b*} y al ser L({a*b*}) regular, que por estar incluido {ak bk / k≥0} deba ser regular también (ojo, antes que lo digas, ta claro que L({ak bk / k≥0}) no lo es).
Esto sobre todo pensando en el diagrama de la Jerarquía de Chomsky.
L({a*b*}) es L3, y si {ak bk / k≥0} ⊂ {a*b*} 
¿no debería ser L({ak bk / k≥0}) L3 también (por inclusión de conjuntos)?
En respuesta a Enrique Galasso Gonzalez

Re: Examen – Julio de 2022 (Ejercicio 1 - Parte b)

de Diego Garat -
hola:

si tu argumento fuese válido, como todo lenguaje es un subconjunto de tiras de sigma*, y sigma* es regular, todo lenguaje sería regular... pero ese no es el caso.

los lenguajes son conjuntos de tiras, ergo sus elementos son cosas del universo sigma*. si yo represento lenguajes en un diagrama de venn en donde el universo son todas las tiras posibles, los lenguajes son círculos (subconjuntos de tiras) y sigma* es el conjunto que engloba a todo el universo.

la jerarquía de chomsky está en otro universo, en donde los elementos son conjuntos de lenguajes, o sea, el universo de los conjuntos de conjuntos de tiras ( 2^sigma* vs sigma*). en ese universo el conjunto máximo es el conjunto de todos los lenguajes que se pueden escribir, los lenguajes en ese universo se representan por puntos, y los conjuntos de lenguajes (como LR) serían los círculos. lo que dice la jerarquía de chomsky es que el conjunto de lenguajes LR está contenido en el conjunto de lenguajes LLC, o sea, todo lenguaje regular es libre de contexto, pero no habla de inclusiones entre esos conjuntos de tiras vistos como elementos.

esto es análogo a los números naturales. yo puedo definir conjuntos en los naturales (N sería sigma*). el conjunto de los pares (N-2), el de los impares (N-2+1), el de los primos(N-p), el de los números menores a 10 (N<10), el de los no primos. pero también puedo hablar de conjuntos de conjuntos de naturales (2^N): por ejemplo, el conjunto de conjuntos finitos (N<10es un elemento de ese conjunto) y  el conjunto de los infinitos ({N-2, N-2+1, N-p...}), entre otros. 

el conjunto de lenguajes finitos es disjunto con el de lenguajes infinitos, pero N<10 (un elemento del primero) tiene elementos en común con N-2, N-2+1, N-p.... de la misma forma, que un lenguaje tenga elementos en común (o esté incluido en) otro lenguaje, no implica de que sean o no del mismo tipo.

saludos,
d.-