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,s₀) una gramática libre de contexto. Un árbol gramatical en G es un árbol ordenado $\mbox{\it Ar\/}$ tal que

• los vértices de $\mbox{\it Ar\/}$ están etiquetados con etiquetas en el alfabeto de la gramática $V\cup T$ o con la etiqueta vacía, $\mbox{\it nil\/}$, y
• cada vértice interior corresponde a una producción en G, es decir, si A es la etiqueta del vértice interior v₀ y $\sigma=[e(v)\vert v\mbox{\rm es hijo de }v_0]$ es la palabra formada por las etiquetas de los hijos de v₀ entonces $(A\rightarrow\sigma)$ es una producción en P.

Un árbol gramatical es de derivación si su raiz está etiquetada con el símbolo inicial s₀ 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{array}{rrcll} 1. & S &\rightarrow& a &\mbox{\it\begin... ...es cerrado por concatenaci\'on. \end{minipage}\/} \end{array}$$

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

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

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

• $\{a^{3n+1}\vert n\geq 0\}$. De hecho, $L(G)\cap a^*=\{a^k\vert k\equiv1\mbox{\rm mod }3\}$.
• $\{a^nbxa\vert n\geq 0,(n\equiv1\mbox{\rm mod }3\Rightarrow x=a),(n\not\equiv1\mbox{\rm mod }3\Rightarrow x=aa)\}$. De hecho, $G\vdash S\stackrel{*}{\rightarrow}a^nbxS$, con $n\geq 0$ y x como antes.
• $\left\{\pi_n\right\}_{n\geq 1}$, donde $\pi_n=aba^2b\cdots ba^nbx_n$ y
  
  $$x_n=\left\{\begin{array}{ll} aaa &\mbox{\rm si $n\equiv 0\mb... ... }3$, } \\ aa &\mbox{\rm en otro caso. } \end{array}\right.$$
  
  

Para concluir esta sección presentaremos las nociones de ambigüedad en gramáticas. Una gramática libre de contexto G=(V,T,P,s₀) 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)²a posee dos derivaciones diestras:

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

2. Si para la gramática G=(V,T,P,s₀) 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'.
Siguiente: Transformaciones equivalentes de gramáticas Un nivel arriba: Arboles de derivación Anterior: Gráficas y árboles