Probabilidad

Lenguajes no regulares
Existen lenguajes que no son regulares y técnicas para demostrarlo: “El lema de bombeo”

Es importante hacer notar que el lema debombeo es una herramienta adecuada para demostrar que un lenguaje no es regular, pero no lo será para demostrar que un lenguaje si es regular (por el hecho deque existen algunos lenguajes no regulares que la cumplen).
Por tanto, si un lenguaje no cumple el lema de bombeo no es regular, pero si lo cumple no podremosdecir si es o no regular.

Enunciado del lema de bombeo
Para todo lenguaje regular infinito L, existe una constante de n, depende de ese lenguaje, deforma que si w es una cadena de L con (w)>=n, podemos partir w en tres cadenas, x , y, z, de forma que:
W=x y z,
Y ≠ ∈ (o dicho de otro modo, que (y)>=l),(x y)<=n
Para cualquier k>=0, la cadena x y k z pertenece a L.
O sea para cualquier cadena de L lo bastante larga, siempre podremos encontrar unapartición en tres subcadenas, con una no vacía en el medio (la y) que no esta demasiado lejos del comienzo de la palabra que podremos “bombear”, es decir, que sise repite la subcadena y cualquier numero de veces, la cadena resultante también pertenecerá a L.
Ejemplo: L ={ 0n1n: n ≥0} no es regular
Idea de lademostración:
•Si L es regular, existe M = (Q, Σ, δ, q0, F) un AFDt que lo reconoce. Además, M tiene un no finito de estados.
•Deben existir 0iy 0jcon i ≠j talesque δ*(q0, 0i) = δ*(q0, 0j)
•Esto significa que δ*(q0, 0i1i) = δ*(q0, 0j1i), pero por un lado 0i1i ∈L y por otro 0j1i ∉L. Llegamos a un contradicción.