Gyzmo escribió:Gracias SICOLOGUS.Ésa es la definición formal,efectivamente.
El caso es que me cuesta ponerla en práctica cuando tengo algún lenguaje.
Por ejemplo,nos preguntamos si el siguiente lenguaje es regular.Suponemos que lo es y aplicamos el lema del bombeo:
L={a^m b^2m}
- n es la constante del lema del bombeo.
- la palabra que elegimos es x:=a^N b^2N
- |x|=3N >= n
y aquí ya se me empieza a ir la olla... ¬_¬
Gracias por contestar.
Creo recordar que va así:
w=a^N b^2N se descompone tal que cumpla lo antes dicho de xyz, entonces, ya que |y|>0, hay 3 posibles casos:
- Que y tenga solo a
- Que y tenga solo b
- Que y tenga a's y b's
Entonces, para cada caso, pruebas separando en trozos la cadena w, por ejemplo el 3º (que creo que es el más difícil) sería:
x=a^r
y=a^s b^t
z=b^u
tal que r+s=N y t+u=2N, con lo que la palabra pertenece al lenguaje.
Entonces bombeas y (eliges tú cuánto bombearlo, lo normal es que sea 0 o 2 o lo que te convenga para que sea fácil demostrarlo), en este caso usamos y^2
xy^2z=a^r a^s b^t a^s b^t b^u, que no pertenece al lenguaje claramente al haber a's y b's intercaladas, por lo que no se cumple el lema de bombeo (después de comprobar que ningún caso es posible, aquí solo hemos visto el tercero) y el lenguaje no es regular.
Espero que más o menos se entienda, me ha sorprendido acordarme xD.