Lenguajes formales

4.7 La clase de los lenguajes incontextuales
4.7.1 Lema del bombeo de los LIs
Teorema. Lema. Aplicaciones.
4.7.2 Operaciones intersección y complementación.

Introducción
Tenemos dos criteriospara saber si un L es I: 1. Cuando existe un AP que lo reconoce; 2. Cuando existe una GI que lo genera.
Para marcar la frontera entre LIs y No Is, diremos que un L es NI cuando no se cumple 1 ocuando no se cumple 2; pero es difícil a veces demostrar la no existencia de un AP o de una GI.
Es más fácil demostrar el incumplimiento de un Lema del Bombeo, que existe para los LIs, lo mismo quesucede con los LRs.
Además estudiar la forma de las palabras en cada clase de Ls da un conocimiento añadido muy importante.

4.7.1 Teorema
La idea de palabra larga se basa siempre en que algo serepite. En el caso de los LRs es el paso por el mismo estado. En el caso de los LIs es una variable en el árbol de derivación durante la generación de la palabra.
La pregunta es: ¿Cuál será la longitud dela palabra más corta para la que se pueda asegurar que se repite una variable? Se podrá asegurar que se repiten variables, al menos una, para todas las palabras que tengan esa longitud o longitudmayor. Todas ellas son palabras largas.
Supongamos que la G tiene n variables. Desde el símbolo privilegiado S hasta una hoja (letra generada) se puede tener un itinerario de longitud n sin que se repitaninguna variable. Si el itinerario tuviese longitud n + 1, es seguro que se repite alguna variable. De acuerdo a esa observación, una palabra de un LI es larga cuando el itinerario más corto paraalcanzar una hoja tiene una longitud = n + 1. La pregunta ahora es: ¿Cuál es la longitud más corta de una palabra larga?
Vamos a suponer que el árbol sintáctico es binario. O sea la GI está puesta enFNCh. Ello no merma la generalidad de los argumentos En el árbol de derivación, de cada nodo habitado por una variable salen dos ramas, excepto el previo a una hoja, del que sale sólo una rama, que...