| dbo:abstract
|
- Viene de Lema del bombeo: Sea un . Entonces existe una constante tal que para toda palabra , con , existe una descomposición tal que: 1.
* 2.
* 3.
* (Indicando la longitud de la palabra, y la repetición de la palabra veces). Este teorema implica que en todo lenguaje libre de contexto, para toda palabra suficientemente larga (), se pueden encontrar una o dos subcadenas izquierda () y derecha (), cuya longitud conjunta es a lo sumo n (), que pueden o bien eliminarse, o bien repetirse simultáneamente las veces que se desee (), 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: 1.
* Suponemos la constante de bombeo. 2.
* Escogemos cuidadosamente una determinada palabra del lenguaje tal que 3.
* Si toda descomposición de , tal que y no pertenece al lenguaje para algún , entonces dicho lenguaje no es libre de contexto.
* Datos: Q5972675 (es)
- Viene de Lema del bombeo: Sea un . Entonces existe una constante tal que para toda palabra , con , existe una descomposición tal que: 1.
* 2.
* 3.
* (Indicando la longitud de la palabra, y la repetición de la palabra veces). Este teorema implica que en todo lenguaje libre de contexto, para toda palabra suficientemente larga (), se pueden encontrar una o dos subcadenas izquierda () y derecha (), cuya longitud conjunta es a lo sumo n (), que pueden o bien eliminarse, o bien repetirse simultáneamente las veces que se desee (), 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: 1.
* Suponemos la constante de bombeo. 2.
* Escogemos cuidadosamente una determinada palabra del lenguaje tal que 3.
* Si toda descomposición de , tal que y no pertenece al lenguaje para algún , entonces dicho lenguaje no es libre de contexto.
* Datos: Q5972675 (es)
|
| rdfs:comment
|
- Viene de Lema del bombeo: Sea un . Entonces existe una constante tal que para toda palabra , con , existe una descomposición tal que: 1.
* 2.
* 3.
* (Indicando la longitud de la palabra, y la repetición de la palabra veces). El contrarrecíproco de este teorema se puede aplicar para demostrar que un lenguaje no es libre de contexto: (es)
- Viene de Lema del bombeo: Sea un . Entonces existe una constante tal que para toda palabra , con , existe una descomposición tal que: 1.
* 2.
* 3.
* (Indicando la longitud de la palabra, y la repetición de la palabra veces). El contrarrecíproco de este teorema se puede aplicar para demostrar que un lenguaje no es libre de contexto: (es)
|
