Arbol de Derivacion

Un árbol de derivación (o árbol sintáctico) es una representación gráfica de como se deriva una forma sentencial a partir del símbolo no-terminal inicial.

Un árbol es un grafo dirigido acíclico en el cual cada nodo se conecta con un nodo distinguido, llamado nodo raíz mediante un único camino. Un nodo n ₁ se dice descendiente de otro nodo n ₂ si se puede llegar a n ₁ a partir de n ₁. El nodo raíz no es descendiente de ningún nodo, y los nodos que no tienen descendientes se denominan hojas. El resto de los nodos se denominan nodos interiores.

Un árbol de derivación tiene las siguientes propiedades:

1. El nodo raíz está rotulado con el símbolo distinguido (inicial) de la Gramatica.
2. Cada hoja corresponde a un símbolo terminal o un símbolo no-terminal.
3. Cada nodo interior corresponde a un símbolo no-terminal.

Un arbol de derivación muestra gráficamente las derivaciones (substituciones de símbolos no terminales) que hay que llevar a cabo para llegar a una Forma Sentencial a partir del símbolo inicial.