Práctica 4: Lenguajes regulares y lema de pumping (Teoría de Lenguajes)

Propiedades

• Lema de pumping: Si L es regular -> $\exists$ n tq $\forall$ w $\in$ L, |w|>=n, w se puede separar en w=xyz tq:
  • y≠λ, |xy|<=n, y $\forall$ k>=0, x.y^k.z $\in$ L.

Ejercicio 05

c) {0^n/n es un numero primo }
Sup. L regular -> Sea a=0. $\exists$ α, β,γ $\in$a*,β≠λ | $\forall$ n, α.β^n.γ$\in$L. Sean: α=a^p, β=a^q, γ=a^r. Como β≠λ -> q≥1. Se debe cumplir que $\forall$n, p+nq+r es primo. Sea n=(p+2q+r+2) -> p+nq+r debe ser primo -> p+nq+r = p+(p+2q+r+2)q+r = p+pq+2q^2+rq+2q+r = (q+1)(p+2q+r) es primo (ABS) -> L NO es regular

e) {x$\in${0, 1}*/x tiene igual cantidad de ceros que de unos}
Sup. L regular -> Sea s = 0^p.1^p $\in$ L y |s| > p. Por el lema de bombeo $\exists$x,y,z | x.y^i.z $\in$ L $\forall$i ≥ 0. Sea x = λ y z = λ, en este caso, xyz $\in$ L, pero se requiere |xy| ≤ p (ABS) -> L NO es regular.

h) {x$\in${0, 1}*/x = x^r}
Sup. L regular -> Sea a=0,b=1. Sup M es un autómata con k estados que lo reconoce. Sea ω=a^k.b^k. Es claro que ω$\in$L -> (2.5) $\exists$ α, β, ρ | αβρ=ω y |αβ|≤k y $\forall$ n, αβ^nρ$\in$L. Como ω=a^k.b^k y |αβ|≤k -> α y β están compuestas sólo de a´s. Por lo tanto, podemos decir que: α=a^t, β=a^s, ρ=a^[k-(s+t)].b^k, donde 1≤ s+t ≤ k y s ≥ 1. Es claro que: αβρ=ω
Como no se hicieron suposiciones adicionales con respecto a las cadenas, decir que $\forall$ n, α.β^n.ρ$\in$L equivale a decir que $\forall$ n, t+ns+k-(s+t)=k. Sin embargo tomando n=0, t+ns+k-(s+t) = t+k-(s+t) = k -> -s = 0. Pero s >= 1 (ABS) -> L no es regular.