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, w=1^p$\in$L. Por lema de bombeo, se puede separar w=xyz tq y≠λ, |xy|<=n. Elijamos p>=n+2, y sea |y|=m<=n -> |xz|=p-m. Como y≠λ -> m≥1. Entonces xy^(p-m)z $\in$ L,pero |xy^(p-m)z| = |xz|+(p-m)|y| = p-m+(p-m)m = (p-m)(m+1), el cual NO es primo, ya que m+1>1 y p-m>=p-n>=n+2-n>=2>1 (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^n.1^n $\in$ L. Usando el lema de bombeo, sea el s=xyz tq y≠λ, |xy|<=n, $\forall$k, x.y^kz $\in$ L. Entonces xy solo tiene 0's, y ademas xz $\in$ L, tiene <n 0's (porque y≠λ) y n 1's (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.