Arboles de derivacion

ARBOLES DE REONOCIMIENTO
Un árbol es un conjunto de puntos, llamados nodos, unidos por líneas, llamadas arcos. Un arco conecta dos nodos distintos. Para ser un árbol un conjunto de nodos y arcosdebe satisfacer ciertas propiedades:
* Hay un único nodo distinguido, llamado raíz (se dibuja en la parte superior) que no tiene arcos incidentes.
* Todo nodo c excepto el nodo raíz estáconectado con un arco a otro nodo k, llamado el padre de c (c es el hijo de k). El padre de un nodo, se dibuja por encima del nodo.
* Todos los nodos están conectados al nodo raíz mediante un únicocamino.
* Los nodos que no tienen hijos se denominan hojas, el resto de los nodos se denominan nodos interiores.

Un árbol de reconocimiento puede ser visto como una representación gráfica de unaderivación, donde el orden en que son aplicadas las producciones es mostrado, debido a la naturaleza jerárquica del árbol.
DERIVACION
La derivación consiste en utilizar una producción, con el fin de irefectuando sustituciones; una sustitución indica que la no terminal -variable sintáctica- situada al lado izquierdo de una producción, es remplazada por la cadena que constituye la parte derechade dicha producción.
La derivación de una sentencia o cadena de un lenguaje, sólo se puede lograr si dicha derivación comienza, a partir del símbolo de inicio o distinguido de la gramática.
El uso dela recursividad al escribir reglas o producciones, es la característica principal que distingue a una gramática con respecto a una expresión regular. Una expresión regular no tiene definicionesrecursivas.
Hay dos tipos de derivación, el primero se llama derivación por la izquierda y consta de estrategias de como remplazar el terminal de más a la izquierda primero, pero contrariamente siaplicamos reglas de forma que derivemos primero el no terminal de la derecha le llamaremos derivación por la derecha
 PROPIEDADES DE UN ÁRBOL DE DERIVACIÓN
Un árbol de reconocimiento tiene las siguientes...