Lenguajes No Regulares

Lenguajes no regulares

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

Ejemplo:L ={ 0n1n: n ≥0} no es 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 de estados.

•Deben existir 0iy 0jcon i ≠j tales que δ*(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.