[2013] [Primer Parcial] [Ejercicio 3] [Parte b] Evitar pumping lemma

[2013] [Primer Parcial] [Ejercicio 3] [Parte b] Evitar pumping lemma

de Mauricio Irace Perez -
Número de respuestas: 2
Buenas,

buscando z me di cuenta de algo y quería preguntar si esta bien el siguiente razonamiento:

sea Lz el siguiente subconjunto de Lb:

 Lz = { a^nb^n | n > 0}

entonces es claro que si tomo el homorfismo h(a)=0,h(b)=1 obtendría que:

 h(Lz)={0^n1^n | n > 0}, lenguaje que no es regular, ya que si lo fuera h(Lz) union {epsilon}= {0^n1^n| n en N} seria regular, (pues {epsilon} es regular y los LR son cerrados por union), pero este es el unico lenguaje que tenemos permitido decir que no es regular. 


Entonces h(Lz) no es regular, luego Lz no es regular, y como Lz es subconjunto de Lb, este tampoco es regular (sino, habria palabras en Lb que no serian descritas ni por autómatas ni por ers(las que estan en Lz))


En respuesta a Mauricio Irace Perez

Re: Ej 3.b de parcial 2013, evitar pumping lemma

de Mauricio Irace Perez -
Me auto corrijo, viendo el mismo parcial, veo que no todo subconjunto de un LR es regular, (Lb esta incluido en La) disculpen las molestias, haré el PL, saludos 
En respuesta a Mauricio Irace Perez

Re: Ej 3.b de parcial 2013, evitar pumping lemma

de Diego Garat -

hola:

efectivamente. es más, todo lenguaje es un subconjunto de sigma*, que es un lenguaje regular. y todo lenguaje, sea regular o no, contiene a un lenguaje regular ---al vacío--- o a cualquier otro de sus subconjuntos que sea finito.


saludos,

d.-