Arboles de derivación

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Existen básicamente dos formas de describir cómo en una cierta gramática una cadena puede ser derivada desde el símbolo inicial.

La forma más simple es listar las cadenas de símbolos consecutivas, comenzando por el símbolo inicial y finalizando con la cadena y las reglas que han sido aplicadas.

Si introducimos estrategias como reemplazar siempre el no terminal de más a la izquierda primero, entonces la lista de reglas aplicadas es suficiente. A esto se le llama derivación por la izquierda. Por ejemplo, si tomamos la siguiente gramática: : (1) S → S + S : (2) S → 1 y la cadena “1 + 1 + 1″, su derivación a la izquierda está en la lista [ (1), (1), (2), (2), (2) ].

Análogamente, la derivación por la derecha se define como la lista que obtenemos si siempre reemplazamos primero el no terminal de más a la derecha. En ese caso, la lista de reglas aplicadas para la derivación de la cadena con la gramática anterior sería la [ (1), (2), (1), (2), (2)].

Sumario

Altura[editar]

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 a es la longitud del lado derecho más largo entre todas las producciones. Dado un arbol T para una cadena alfa, vale que , donde h es la altura del arbol.

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 , cumple la HI; y como se deriva a partir de expandiendo a lo sumo simbolos no terminales, entonces .