Lema de bombeo para lenguajes regulares
|
Contenido de esta página:
Lema de bombeo
Sea L un lenguaje regular, entonces existe una
constante
$$ n_0 \in \mathbb{N} $$
tal que cualquier palabra w del lenguaje L cuya longitud sea
$$ |w| \geq n_0 $$
se puede descomponer en tres cadenas,
$$ w = xyz $$
cumpliendo:
-
$$ |xy| \leq n_0 $$
-
y no es la palabra vacía, es decir,
$$ y \neq \varepsilon $$
-
La palabra
$$ xy^m z \in L, \ \forall m\in \mathbb{N}$$
El lema recibe este nombre ya que la cadena y se puede bombear
en la palabra w, ya sea repitiéndose tantas veces como se desee u omitiéndose,
de modo que la nueva palabra sigue perteneciendo al lenguaje L.
Omitimos la demostración del lema ya que podemos consultarla en un gran número de textos.
También existe otro lema con el mismo nombre, y la misma idea, para los lenguajes independientes
del contexto (LIC).
Aplicación del Lema de bombeo
El lema se utiliza básicamente para demostrar que un determinado lenguaje L no es
regular. Normalmente, se supone que el lenguaje es regular y se aplica el lema hasta
llegar a una contradicción (reducción al absurdo).
Vamos a ver ejemplos de esta aplicación para los siguientes lenguajes.
Problema 1
El lenguaje formado por n ceros seguidos de n unos, es decir,
$$ L = \{ 0^n 1^n\ :\ n\geq 1,\ n\in \mathbb{N} \} $$
Ver solución
Sea
$$ n_0 \in \mathbb{N} $$
la constante del lema de bombeo.
Consideremos la palabra
$$ w = 0^k 1^k $$
siendo
$$ k = n_0 $$
Es evidente que w es una palabra del lenguaje y su longitud es
$$ |w|=k+k=n_0+n_0 = 2n_0 \geq n_0 $$
Supongamos que
$$ w=xyz $$
es una descomposición que cumple las condiciones del lema.
La primera condición es
$$ |xy| \leq n_0 $$
Pero como
$$ k=n_0 $$
necesariamente,
$$ xy = 0^p $$
siendo
$$ p\leq n_0 = k $$
Por tanto,
$$ w = 0^p 0^{k-p} 1 ^k $$
Como, por la segunda condición, y no puede ser la palabra vacía
$$ xy = 0^p = 0^{p_1}0^{p_2}$$
$$ z = 0^{k-p} 1^k $$
donde
$$ p_1 + p_2 = p \leq n_0,\ p_2 \neq 0 $$
El lema nos dice que
$$ \forall m \in \mathbb{N},\ xy^m z\in L $$
Entonces, la palabra
$$ xy^m z = 0^{p_1}(0^{p_2})^m 0^{k-p} 1^k $$
debería pertenecer al lenguaje para cualquier m. Esto no es cierto,
por ejemplo, si m = 2 ya que el número de ceros es
$$ p_1 + mp_2 +k -p = p_1 +p_2 +p_2 +k-p = $$
$$ p+p_2 +k -p = k+p_2 > k $$
Es decir, hay más ceros que unos. La palabra no
pertenece al lenguaje.
Como hemos llegado a una contradicción, el lenguaje no
es regular.
Problema 2
$$ L = \{ 0^k 1 0^k :\ k\geq 1,\ k\in\mathbb{N} \} $$
Ver solución
Sea
$$ n_0 \in \mathbb{N} $$
la constante del lema de bombeo.
Consideremos la palabra
$$ w=0^k10^k,\ k=n_0 $$
que obviamente es una palabra del lenguaje.
Sea
$$ w = xyz $$
una descomposición que cumple las condiciones
del lema.
Por la primera condición,
$$ |xy| \leq n_0 \rightarrow xy=0^p $$
$$ p \leq k = n_0 $$
Entonces,
$$ x = 0^{p_1},\ y = 0^{p_2},\ p_1+p_2 = p $$
$$ z = 0^{k-p}10^k $$
Además, por la segunda condición,
$$ p_2 \neq 0 $$
La descomposición es
$$ w = xyz = 0^{p_1}0^{p_2} 0^{k-p}10^k $$
Aplicando el lema, la palabra
$$ xy^mz = 0^{p_1}(0^{p_2})^m 0^{k-p}10^k $$
debería pertenecer al lenguaje para cualquier m.
Pero esto no es cierto, por ejemplo, para m = 2 ya que
el número de ceros a la izquierda del 1 es
$$ p_1+ 2p_2 +k-p = p_1 +p_2+p_2 +k-p = $$
$$ = p+p_2 +k-p = p_2 +k > k $$
que es mayor que el número de ceros a la derecha del 1.
Por tanto, el lema no se cumple, lo que quiere
decir que el lenguaje L no es regular.
Problema 3
El lenguaje de palabras formadas por un cuadrado perfecto de ceros, esto es,
$$ L = \{ 0^n :\ n=k^2,\ k\in\mathbb{N} \} $$
Ver solución
Los cuadrados perfectos son
$$ 1^2,\ 2^2, \ 3^2,\ ... $$
es decir,
$$ n^2,\ n \in \mathbb{N} $$
Sea
$$ n_0 \in \mathbb{N} $$
la constante del lema de bombeo.
Sea w la palabra del lenguaje L
$$ w = 0^k, \ k={n_0}^2 $$
Y sea
$$ w = xyz $$
una descomposición acorde con el lema.
Por la primera condición,
$$ |xy|\leq n_0 \rightarrow 0< |y| \leq n_0 $$
La desigualdad estricta se debe a la segunda condición
del lema.
Aplicando el lema, la palabra
$$ xy^2z $$
es (o debería) ser una palabra del lenguaje.
Su longitud es
$$ |xy^2 z| = |xyz| +|y| = {n_0}^2 +|y| $$
Además, como
$$ |y| > 0 $$
tenemos la desigualdad estricta
$$ |xy^2 z| > |xyz| $$
Por tanto,
$$ {n_0}^2 = |xyz| < |xy^2 z| < {n_0}^2 + n_0 $$
Pero
$$ (n_0 +1)^2 = {n_0}^2 +2n_0 + 1 > {n_0}^2 +n_0 $$
Así que
$$ {n_0}^2 < |xy^2 z| < (n_0 +1)^2 $$
Es decir, la longitud de la palabra está entre dos cuadrados perfectos consecutivos y,
por tanto, no puede ser un cuadrado perfecto.
El lenguaje L no es regular por reducción
al absurdo.
Problema 4
El lenguaje formado por las palabras de un cubo perfecto de ceros, es decir,
$$ L = \{ 0^n :\ n=k^3,\ k\in\mathbb{N} \} $$
Ver solución
Los cubos perfectos son
$$ n^3,\ n\in \mathbb{N} $$
Sea
$$ n_0 \in \mathbb{N} $$
la constante del lema de bombeo.
Consideremos la palabra del lenguaje L
$$ w = 0^k,\ k={n_0}^3 $$
y sea
$$ w = xyz $$
una descomposición según el lema de bombeo.
Por la primera y segunda condición,
$$ |xy| \leq n_0 \rightarrow 0 < |y | \leq n_0 $$
Aplicando el lema, la palabra
$$ xy^m z \in L, \ \forall m \in \mathbb{N} $$
En particular, para m = 3 tenemos
$$ {n_0}^3 = |xyz| < |xy^3 z| = $$
$$ = |xyz|+2|y| = {n_0}^3 +2|y| \leq $$
$$ \leq {n_0}^3 +2n_0 $$
Es decir,
$$ {n_0}^3 < |xy^3 z| \leq {n_0}^3 + 2n_0 $$
Teniendo en cuenta que
$$ (n_0 +1)^3 = {n_0}^3 +3{n_0}^2 +3n_0 +1 $$
Obviamente,
$$ {n_0}^3 +2n_0 < {n_0}^3 +3{n_0}^2 +3n_0 +1 $$
con lo que podemos escribir
$$ {n_0}^3 < |xy^3 z| < (n_0 +1)^3 $$
La longitud de la palabra está entre dos cubos perfectos
consecutivos. Por tanto, dicha palabra no forma
parte del lenguaje L.
El lema de bombeo no se cumple, así que L no
es un lenguaje regular.
Inicio
Matesfacil.com
by J. Llopis is licensed under a
Creative
Commons Attribution-NonCommercial 4.0 International License.
