Lema del bombeo para lenguajes libres del contexto

En ciencia de la computación, en particular en la teoría de lenguajes formales, el lema del bombeo para lenguajes libres del contexto, también conocido como lema de Bar-Hille, es un lema que brinda una propiedad compartida por todos los lenguajes libres del contexto y generaliza el lema del bombeo para lenguajes regulares. Como el lema del bombeo no garantiza que el lenguaje sea libre del contexto, existen condiciones necesarias más fuertes, como el lema de Ogden.

Declaración formal

Idea de la demostración: Si s es suficientemente larga, su árbol de derivación w.r.t. una formal normal de Chomsky debe contener algún no-terminal N dos veces en algún camino del árbol (imagen superior). Repitiendo n veces la parte de la derivación N ⇒...⇒ vNx se obtiene una derivación para uvnwxny (imágenes situadas abajo a izquierda y a la derecha respectivamente para n=0 y 2).

Si un lenguaje L es libre del contexto, entonces existe un entero p >= 1 (llamado longitud de bombeo) tal que toda cadena s en L que tiene una longitud de p o más símbolos (|s| > p) puede ser escrita como:

s = uvwxy

Con subcadenas u, v, w, x y y, tal que:

1. |vwx| ≤ p

2. |vx| ≥ 1

3. uvⁿwxⁿy ∈ L para todo n ≥ 0

Debajo está una expresión formal del Lema de Bombeo.

${\begin{array}{l}(\forall L\subseteq \Sigma ^{*})\\\quad ({\mbox{ libre del contexto }}(L)\Rightarrow \\\quad ((\exists p\geq 1)((\forall s\in L)((|s|\geq p)\Rightarrow \\\quad ((\exists u,v,w,x,y\in \Sigma ^{*})(s=uvwxy\land |vwx|\leq p\land |vx|\geq 1\land (\forall n\geq 0)(uv^{n}wx^{n}y\in L)))))))\end{array}}$

Explicación y declaración informal

El lema del bombeo para lenguajes libres del contexto (llamado solo “el lema del bombeo” en el resto de este artículo) describe una propiedad que todos los lenguajes libres del contexto garantizan cumplir.

La propiedad es una propiedad de todas las cadenas en el lenguaje que son de longitud al menos p, donde p es una constante-llamada longitud del bombeo- que varía entre lenguajes libres del contexto.

Digamos que s es una cadena de longitud al menos p que está en el lenguaje.

El lema del bombeo establece que s puede ser dividida en 5 subcadenas, s=uvwxy, donde vx es no vacío y la longitud de vwx es como máximo p, tal que repitiendo v y x cualquier (y el mismo) número de veces en s produce una cadena que está todavía en el lenguaje (esto es posible y a menudo útil repetir cero veces, lo cual elimina v y x de la cadena). Este proceso de “bombear” copias adicionales de v y x es lo que le da al lema del bombeo su nombre.

Los lenguajes finitos (los cuales son regulares y por lo tanto libres del contexto) cumplen el lema del bombeo trivialmente haciendo p igual a la longitud de la cadena de mayor longitud en L más uno. Como no hay cadenas de esta longitud el lema del bombeo no es violado.

Uso del lema

El lema del bombeo es frecuentemente usado para probar que un lenguaje dado L no es libre del contexto, mostrando que arbitrariamente largas cadenas s están en L que no pueden ser “bombeadas” sin producir cadenas fuera de L.

Por ejemplo, el lenguaje L = { aⁿbⁿcⁿ | n > 0 } se puede mostrar que no es libre del contexto usando el lema del bombeo en una reducción al absurdo. Primero, se asume que L es libre del contexto. Por el lema del bombeo, existe un entero p que es la longitud de bombeo del lenguaje L. Sea la cadena s = a^pb^pc^p in L. El lema del bombeo plantea que s puede ser escrito en la forma s=uvwxy, donde u,v,w,x,y son subcadenas, tal que |vwx| ≤ p, |vx| ≥ 1, uvⁱwxⁱy ∈ L para todo entero i ≥ 0. Mediante la selección de s y el hecho de que |vwx| ≤ p, es fácil ver que la subcadena vwx no puede contener más de 2 símbolos distintos. Luego, tenemos una de 5 posibilidades para vwx:

vwx = a^j Para algún j ≤ p.
vwx = a^jb^k Para algún j y k con j+k ≤ p.
vwx = b^j Para algún j ≤ p.
vwx = b^jc^k Para algún j y k con j+k ≤ p.
vwx = c^j Para algún j ≤ p.

Para cada caso, es fácilmente verificable que uvⁱwxⁱy no contiene iguales números de cada letra para cualquier i ≠ 1. Por lo tanto, uv²wx²y no tiene la forma aⁱbⁱcⁱ. Esto contradice la definición de L. Luego, la asunción inicial de que L es libre del contexto es falsa.

Mientras que el lema del bombeo es a menudo una útil herramienta para probar que un lenguaje dado no es libre del contexto, este no ofrece una caracterización completa de los lenguajes libres del contexto. Si un lenguaje no satisface la condición dada por dicho lema, se establece que no es libre del contexto.

Por otra parte, existen lenguajes que no son libres del contexto, y, sin embargo, satisfacen la condición dada por el lema del bombeo, por ejemplo L = { b^jc^kd^l | j, k, l ∈ ℕ } ∪ { aⁱb^jc^jd^j | i, j ∈ ℕ, i≥1 }: para s=b^jc^kd^l con por ejemplo j≥1 se selecciona vwx que consiste solo de b’s, for s=aⁱb^jc^jd^j se selecciona vwx que consiste solo de a’s; en ambos casos todas las cadenas bombeadas están todavía en L.

Referencias

Barra-Hillel, Y. Bar-Hillel (1964). Language and Information: Selected Essays on their Theory and Application. Addison-Wesley. pp. 116-150. ISBN 0201003732. OCLC 783543642. ; «On formal properties of simple phrase-structure grammars». Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14 (2): 143-172. 1961. ; (1961). "En propiedades formales de frase sencilla-gramáticas de estructura". Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung. (2): 143@–172. — Reprinted En: Y. (1964). Lengua e Información: Seleccionó Ensayos en su Teoría y Aplicación. Addison-Wesley serie en lógica. Addison-Wesley. pp.
Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. (1997). PWS Publicando. Sección 1.4: Nonregular Lenguas, pp. 77@–83. Sección 2.3: No-contexto-Lenguas libres, pp. 115@–119.

Datos: Q2596624