next up previous contents
Siguiente: Transformaciones equivalentes de gramáticas Un nivel arriba: Arboles de derivación Anterior: Gráficas y árboles

Arboles y gramáticas

Sea G=(V,T,P,s0) una gramática libre de contexto. Un árbol gramatical en G es un árbol ordenado $\mbox{\it Ar\/}$ tal que Un árbol gramatical es de derivación si su raiz está etiquetada con el símbolo inicial s0 y todas sus hojas tienen etiquetas terminales o vacía. La leyenda de un árbol de derivación es la palabra obtenida al concatenar ordenadamente, con cualquier orden de izquierda a derecha, las etiquetas de sus hojas. Así pues, todo árbol de derivación tiene como leyenda una palabra en L(G). Recíprocamente, para cada palabra $\sigma$ en L(G) existe un árbol de derivación cuya leyenda coincide con $\sigma$. Si $\sigma=\sigma_1A\sigma_2$ y $\tau=\sigma_1\beta\sigma_2$, donde $(A\rightarrow\beta)$ es una producción en P y $\sigma_2$ consiste únicamente de símbolos terminales, decimos que $\tau$ se sigue de $\sigma$ por la aplicación diestra de una producción. Una derivación es diestra si todas las aplicaciones de producciones hechas son diestras. Las derivaciones siniestras se definen simétricamente. Ejemplo. Consideremos las siguientes producciones:

\begin{displaymath}\begin{array}{rrcll}
1. & S &\rightarrow& a &\mbox{\it\begin...
...es cerrado por concatenaci\'on.
\end{minipage}\/}
\end{array}\end{displaymath}

Sendas derivaciones siniestra y diestra de la palabra a(ba2)2=abaabaa son las siguientes:

\begin{displaymath}\begin{array}{\vert\vert l\vert\vert r\vert\vert}\hline \hlin...
...ay}abaa \\
abaabaa & abaabaa \\
\hline \hline
\end{array}\end{displaymath}

En el lenguaje L(G) generado por esta gramática se encuentran incluidos los siguientes lenguajes:


Para concluir esta sección presentaremos las nociones de ambigüedad en gramáticas. Una gramática libre de contexto G=(V,T,P,s0) se dice ser ambigua si alguna palabra de su lenguaje, $\sigma\in L(G)$ posee dos derivaciones diestras. Ejemplos. 1. La gramática G cuyas producciones son $S\rightarrow SbS\vert a$ es ambigua pues la palabra (ab)2a posee dos derivaciones diestras:

\begin{displaymath}\begin{array}{\vert\vert l\vert\vert l\vert\vert}\hline \hlin...
...\end{array} \\
ababa & ababa \\
\hline \hline
\end{array}\end{displaymath}




2. Si para la gramática G=(V,T,P,s0) incluimos una copia V' del conjunto de variables no-iniciales más copias de las producciones de P con símbolos en S' entonces la nueva gramática $G'=(V\cup V', T, P\cup P', s_0)$ es ambigua pues cada derivación diestra puede derivarse considerando símbolos en V o en su contraparte V'.
next up previous contents
Siguiente: Transformaciones equivalentes de gramáticas Un nivel arriba: Arboles de derivación Anterior: Gráficas y árboles
Guillermo Morales-Luna
2000-06-27