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

Ejercicio 05

c) Sup. L regular -> Sea a=0. $\exists$ α$\in$a*, β $\in$a*,γ$\in$a*,β≠λ tq $\forall$ n, αβ^nγ$\in$L. Sean: α=a^p, β=a^q, γ=a^r. Como β≠λ -> q≥1. Se debe cumplir que para todo 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. Pero q≥1 -> q+1 ≥ 2 y (p+2*1+r) ≥ 2〉 = FALSO -> L NO es regular