Tarea

Lenguajes no regulares

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

Ejemplo:L ={ 0n1n: n ≥0} noes regular

Idea de la demostración:

•Si L es regular, existe M = (Q, Σ, δ, q0, F) un AFDt que lo reconoce. Además, M tiene un nofinito deestados.

•Deben existir 0iy 0jcon i ≠j tales que δ*(q0, 0i) = δ*(q0, 0j)

•Esto significa que δ*(q0, 0i1i) = δ*(q0, 0j1i), pero por un lado0i1i ∈L y por otro 0j1i ∉L. Llegamos a un contradicción.
Gracias al lema de bombeo podremos demostrar que ciertos lenguajes no son regulares.Esimportante hacer notar que el lema de bombeo es una herramienta adecuada parademostrar que un lenguaje no es regular, pero no lo será para demostrarque un lenguaje sies regular. Por tanto, si un lenguaje

no cumple el lema de bombeo no es regular, pero silocumple no podremos decir si es ono regular.
Sea el lenguaje L = {a 2n b n | n ≥ 0}. Demostrar que L no es reg
ular.1.

Suponemos que el lenguaje es regular. Si lo es, y comoes infinito, para él se cumpliráel lema de bombeo. Sea por tanto n
∈
N la constante del lema de bombeo para L.Elijo una palabra que pertenezca aL y de longitud mayor o igual a n:w = a 2n b n ,tenemos que w
∈

L y |w| = 3n y por tanto |w| ≥ n, sea cual sea n.
2.

Ahora tenemos queencontrar todas las formas de partir la palabra elegida w entres xyz que cumplan las restricciones del lema de bombeo:- w = xyz-
y ≠ ε
- |xy|