Árboles de derivación

Un árbol de derivación es una forma de visualizar las relaciones que tienen las cabezas de reglas junto con los cuerpos de estas. En un árbol de derivación, los elementos del cuerpo de una regla se convierte en nodos hijos de la cabeza de la regla.

Ejemplo árbol de derivación para la cadena aaabbb #

Para la gramática \( S \rightarrow aSb | \varepsilon \) y la cadena aaabbb el árbol de derivación es:

Árbol de derivación para la cadena 'aaabbb'

Para este ejemplo, sólo tenemos una derivación posible y sólo tenemos un árbol de derivación.

Ejemplo árbol de derivación para la cadena (a*ba*ba*)* #

Para la gramática \[ \begin{array}{rl} R\rightarrow & B\\ R\rightarrow & R+R\\ R\rightarrow & R^*\\ R\rightarrow & RR\\ R\rightarrow & (R)\\ B\rightarrow & a\\ B\rightarrow & b\\ B\rightarrow & \epsilon\\ B\rightarrow & \emptyset\\ \end{array} \] y las derivaciones de la cadena \((a^*ba^*ba^*)^* \) vistas en la sección anterior el árbol de derivación resulta:

Árbol de derivación para ER de número par de bes

En este caso varias derivaciones pueden resultar en un sólo árbol de derivación. Sin embargo, esta gramática tiene múltiples derivaciones y alguna otras generan otros árboles de derivación.

Todos los árboles de derivación (28) para ER de número par de bes

En resumen

Para una gramática G un cadena puede tener múltiples derivaciones, dependiendo de la estrategia de sustitución que se elija; algunas de estas derivaciones resultarán en un solo árbol de derivación; sin embargo, es posible que algunas derivaciones de la cadena resulten en múltiples árboles de derivación, por lo tanto una cadena tenga asociadas múltiples árboles de derivación.

comments powered by Disqus