Edición de «Demostraciones (Teoría de Lenguajes)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 54: | Línea 54: | ||
== Lema de Pumping (LIC) == | == Lema de Pumping (LIC) == | ||
=== Altura del | === Altura del arbol === | ||
La altura del | La altura del arbol de derivacion es la longitud del camino más largo en el arbol de derivacion tal que comienza en la raiz y el final es una hoja (definicion natural de arbol). Vale que la hoja siempre es un terminal. Notar que en el arbol de derivacion, la base (hojas leidas en preorder) es igual a la cadena derivada. | ||
Sea una gramatica donde | Sea una gramatica donde ''a'' es la longitud del lado derecho más largo entre todas las producciones. Dado un arbol T para una cadena alfa, vale que <math>| \alpha | \leq a^h</math>, donde ''h'' es la altura del arbol. | ||
La | La demostracion se hace por induccion sobre la altura. El caso base con h = 0 es trivial. El paso inductivo se basa que la base correspondiente a la altura ''h'', llamemosla <math>\gamma</math>, cumple la HI; y como <math>\alpha</math> se deriva a partir de <math>\gamma</math> expandiendo a lo sumo <math>| \gamma |</math> simbolos no terminales, entonces <math>| \alpha | \leq a * | \gamma |</math>. | ||
=== Pumping (LIC) === | === Pumping (LIC) === |