Lema del bombeo para gramáticas independientes del contexto

Lema del bombeo para gramáticas independientes del contexto: Viene de Lema del bombeo:

Sea $\mbox{L}\,$ un lenguaje libre de contexto. Entonces existe una constante $n \in \mbox{N}$ tal que para toda palabra $x \in \mbox{L}$ , con $|x| \ge n\,$ , existe una descomposición $x=yzuvw\,$ tal que:

$|z u v| \le n\,$

$|z v|>0\,$

$\forall i \ge 0, x=y z^i u v^i w \in \mbox{L}\,$

(Indicando $|x|\,$ la longitud de la palabra, y $x^i\,$ la repetición de la palabra $x\,$ $i\,$ veces).

Este teorema implica que en todo lenguaje libre de contexto, para toda palabra suficientemente larga ( $|x| \ge n\,$ ), se pueden encontrar una o dos subcadenas izquierda ( $z\,$ ) y derecha ( $v\,$ ), cuya longitud conjunta es a lo sumo n ( $|z u v| \le n\,$ ), que pueden o bien eliminarse, o bien repetirse simultáneamente las veces que se desee ( $y z^i u v^i w\,$ ), obteniendo de dicha forma palabras que también pertenecen al lenguaje.

El contrarrecíproco de este teorema se puede aplicar para demostrar que un lenguaje no es libre de contexto:

Suponemos $n\,$ la constante de bombeo.

Escogemos cuidadosamente una determinada palabra del lenguaje tal que $|x| \ge n\,$

Si encontramos una descomposición $|z u v| \le n, |z v|>0\,$ tal que alguna de las palabras $y z^i u v^i w , i \ge 0\,$ no pertenece al lenguaje, entonces dicho lenguaje no es libre de contexto.

Categorías:
Lenguajes formales
Lemas (matemáticas)

Игры ⚽ Поможем решить контрольную работу

Lema del bombeo — En la teoría de lenguajes formales de la teoría de la computación, el lema de bombeo establece que en un lenguaje, cualquier cadena de caracteres de por lo menos una cierta longitud (llamada longitud de bombeo), contiene una sección que puede ser … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico