Tarea

Un árbol con raíz es un tipo muy particular de grafo no-dirigido; está formado por un conjunto de vértices o nodos conectados entre sí por arcos o aristas, con la siguiente propiedad: existe un nodoespecial, llamado la raíz del árbol, tal que hay una única trayectoria entre cualquier nodo y la raíz. De esta manera, la raíz se ramifica en nodos, llamados descendientes inmediatos, cada uno de loscuales puede tener, a su vez, descendientes inmediatos, y así sucesivamente. La propiedad que caracteriza a un árbol garantiza que un nodo puede tener 0, 1, o más descendientes inmediatos pero unúnico antecesor inmediato. El único nodo que no tiene antecesores es la raíz. Los nodos que tienen descendientes, excepto la raíz, se denominan nodos interiores. Los nodos que no tienen descendientes sellaman hojas del árbol. En la terminóloga usualmente utilizada, los descendientes de un nodo también se denominan hijos y los antecesores padres o ancestros. El numero de vértices (y por lo tanto, elnumero de arcos) de un árbol puede ser infinito.
 
El árbol de una derivación S ∗⇒ w, w ∈ Σ ∗ , en una GIC es un árbol con raíz que se forma de la siguiente manera:
1. La raíz esta etiquetada conel símbolo inicial S.
2. Cada nodo interior esta etiquetado con un no terminal.
3. Cada hoja esta etiquetada con terminal o con λ.
4. Si en la derivación se utiliza la producción A → S1S2 ... Sk,donde Si ∈ (V ∪Σ)∗ , el nodo A tiene k descendientes inmediatos: S1, S2,. . . , Sk, escritos de izquierda a derecha.
De esta forma, las hojas del árbol de derivación de S ∗⇒ w son precisamente lossímbolos de la cadena w, ledos de izquierda a derecha y, posiblemente, algunos λ.
La búsqueda de un árbol de derivación para una cadena w ∈ Σ ∗ se denomina análisis sintáctico de w. Los arboles dederivación también se suelen llamar arboles sintácticos o arboles de análisis sintáctico.

El anterior es también el árbol de la derivación
S ⇒ AB ⇒ aB ⇒ abBa ⇒ abba
Esto muestra que dos...