Tengo una duda sobre la demostración del lema del bombeo para lenguajes libres de contexto. El lema del bombeo para lenguajes libres de contexto se enuncia de la siguiente manera:
Si $A$ es un lenguaje libre de contexto, entonces existe un número $p$ (la longitud de bombeo) donde, si $s$ es una cadena en $A$ cuya longitud es al menos $p$, entonces $s$ puede dividirse en cinco partes $s = uvxyz$ que satisfacen las condiciones:
- para todo $i\geq 0$, $uv^ixy^iz \in A$,
- $|vy|>0$, y
- $|vxy| \leq p$
La demostración es la siguiente:
Sea $G$ una gramática libre de contexto para el lenguaje libre de contexto $A$. Sea $b$ el número máximo de símbolos en el lado derecho de una regla. Por lo tanto, en cualquier árbol sintáctico que use esta gramática, un nodo puede tener como máximo $b$ hijos. Por lo tanto, si la altura del árbol sintáctico es a lo sumo $h$, la longitud de bombeo de la cadena generada es a lo sumo $b^h$. Recíprocamente, si una cadena generada tiene una longitud de al menos $b^h+1$, cada uno de sus árboles sintácticos debe tener una altura de al menos $h+1$.
Sea $|V|$ el número de variables (símbolos no terminales) de $G$. Sea $p$, la longitud de bombeo, sea $b^{|V|} + 1$. Ahora, si $s$ es una cadena en $A$ y su longitud es de $p$ o más, su árbol sintáctico debe tener una altura de al menos $|V|+1$.
Para ver cómo bombear cualquiera de estas cadenas $s$, sea $\tau$ una de sus árboles sintácticos que tiene el menor número de nodos. Sabemos que $\tau$ tiene altura, al menos, $|V|+1$, por lo tanto debe contener un camino desde la raíz hasta una hoja de longitud al menos $|V|+1$. Este camino tiene al menos $|V|+2$ nodos, uno en un símbolo terminal y los demás en variables. Así que, este camino tiene al menos $|V|+1$ variables. Por el principio de la casilla del palomo, alguna variable $R$ aparece más de una vez en este camino. Sea $R$ una variable que se repite entre las $|V|+1$ variables más bajas en este camino.
Luego, se muestran las demostraciones para las condiciones 1, 2 y 3. No transcribiré las demostraciones para la condición 1 y 2, porque las entendí. Mi problema está con la condición 3:
Para obtener la condición 3, debemos estar seguros de que $vxy$ tiene una longitud de como máximo $p$. En el árbol sintáctico de $s$, la ocurrencia superior de $R$ genera $vxy$. Elegimos $R$ de manera que ambas ocurrencias estén entre las $|V|+1$ variables más bajas en el camino, y elegimos el camino más largo en el árbol, por lo que el subárbol donde $R$ genera $vxy$ tiene una altura como máximo $|V|+1$. Un árbol con esta altura puede generar una cadena de longitud como máximo $b^{|V|+1} = p$.
Estoy confundido sobre el último párrafo. Inicialmente, elige que la longitud de bombeo sea $b^{|V|} + 1$, y concluye que la altura de cada árbol sintáctico de $s$ con $|s| \geq p$ es como máximo $|V|+1$. Sin embargo, después, concluye que, dado que el subárbol donde $R$ genera $vxy$ tiene una altura como máximo $|V| + 1$, la cadena generada por este subárbol tiene una longitud como máximo $b^{|V|+1} = p$. ¿Pero no es $p = b^{|V|} +1$?
