next up previous contents
Siguiente: Ejercicios Un nivel arriba: Gramáticas formales Anterior: Ejemplos

Tipos de gramáticas

En el estudio de las gramáticas formales y de sus correspondientes lenguajes aparecen varios problemas, entre los que se cuentan a los siguientes:

Problema 4.1 (de la Palabra)   Dada una gramática G y una palabra $\sigma$ sobre su alfabeto de símbolos terminales, decidir si acaso la palabra pertenece o no al lenguaje generado por G.

Problema 4.2 (de Derivación)   Dada una gramática G y una $\sigma\in L(G)$ encontrar una derivación en G de $\sigma$ a partir del símbolo inicial de G.

Problema 4.3 (Formalización de un lenguaje)   Dado un lenguaje L encontrar una gramática G tal que L(G)=L, es decir, tal que genere al lenguaje L.

Estos problemas pueden ser muy complejos, e irresolubles, en general, si consideramos como ``decidir'' el aplicar un procedimiento efectivo, en el sentido de Church, que en un número finito de transformaciones simbólicas nos dé una respuesta positiva o negativa al problema planteado. En toda clase de gramáticas es de suma importancia decidir la resolubilidad de los anteriores problemas y, en el caso de que sean resolubles, calcular la complejidad de los procedimientos para resolverlos. En la definición siguiente presentamos algunas clases de gramáticas, las cuales coinciden con las ya presentadas en la tabla (4). Una gramática G=(V,T,P,s0) se dice ser
irrestricta
si $P\subset V^+\times (V\cup T)^*$, es decir, las producciones de la gramática tienen como antecedentes palabras no-vacías de símbolos variables,
sensible al contexto con borro
si las producciones de la gramática son de la forma $\sigma A\tau\rightarrow \sigma \alpha\tau$, donde $A\in V$ y $\alpha,\sigma,\tau\in(V\cup T)^*$,
sensible al contexto
si las producciones de la gramática son de una cualquiera de las formas siguientes,
1.
$\sigma A\tau\rightarrow \sigma \alpha\tau$, donde $A\in V$, $\sigma,\tau\in(V\cup T)^*$ y $\alpha\in(V\cup T)^+$,
2.
$s_0\rightarrow \mbox{\it nil\/}$,
y además s0 no aparece como consecuente en ninguna producción,
libre de contexto
si las producciones de la gramática son de la forma $A\rightarrow \alpha$, donde $A\in V$ y $\alpha\in(V\cup T)^*$,
LR(k)
si la gramática es libre de contexto y además satisface las restricciones enunciadas a continuación. i) El símbolo inicial no se deriva de sí mismo mediante reglas que preserven la longitud de palabras derivadas. ii) Para cualesquiera variables $A_1,A_2\in V$ y cualesquiera palabras $\sigma_1,\sigma_2,\tau_1,\tau_2\in (V+T)^*$ y $\upsilon_1,\upsilon_2\in T^*$ rige la implicación siguiente:

\begin{displaymath}\left.\begin{array}{c}
\begin{array}{rclrcl}
S &\stackrel{*...
...igma_1 &=& \sigma_2 \\
\tau_1 &=& \tau_2
\end{array}\right.\end{displaymath}

donde para cada palabra $\sigma$ denotamos por $\left.\sigma\right\vert _{n}$ al mayor prefijo de $\sigma$ con longitud a lo sumo n.
LL(k)
si la gramática es libre de contexto y además satisface la restricción enunciada a continuación. Para cualquier variable $A_1\in V$ y cualesquiera palabras $\tau_1,\tau_2,\upsilon_1,\upsilon_2\in (V+T)^*$ y $\sigma,\phi_1,\phi_2\in T^*$ rige la implicación siguiente:

\begin{displaymath}\left.\begin{array}{c}
\begin{array}{rclrclrcl}
S &\stackre...
...k}
\end{array}\right\} \ \ \ \Rightarrow\ \ \
\tau_1=\tau_2.\end{displaymath}

Las gramáticas del tipo LL(k) o LR(k) se dicen ser gramáticas libres de contexto deterministas.
lineal
si las producciones de la gramática son de la forma $A\rightarrow \alpha B \beta$ o $A\rightarrow \alpha$, donde $A,B\in V$ y $\alpha,\beta\in T^*$,
lateral
si las producciones de la gramática son todas de la forma $A\rightarrow \alpha B$ o $A\rightarrow \alpha$, donde $A,B\in V$ y $\alpha,\beta\in T^*$, en cuyo caso la gramática es derecha, o bien son todas de la forma $A\rightarrow B \alpha$ o $A\rightarrow \alpha$, en cuyo caso la gramática es izquierda.
Puede verse que las clases de gramáticas así definidas forman una jerarquía en el siguiente sentido:

\begin{displaymath}\left.\begin{array}{c}
\mbox{\it lineal derecha\/} \\
\Upd...
...x{\it SCB\/} & \Rightarrow &
\mbox{\it tipo 0\/}
\end{array}\end{displaymath}

Cada una de las implicaciones mostradas es estricta pues sus recíprocos no son válidos según lo atestiguan contraejemplos apropiados que iremos presentando a lo largo de este curso. Un lenguaje L se dice ser del mismo tipo que una gramática que lo genere. Para concluir esta sección presentamos en la proposición siguiente una manera de re-escribir gramáticas que será de utilidad posteriormente.

Proposición 4.1   Para toda gramática $G_1=\left(V_1,T_1, P_1,s_{01}\right)$ y exite una gramática equivalente $G_2=\left(V_2,T_2, P_2,s_{02}\right)$, con el mismo conjunto de símbolos terminales T2=T1, tal que en la nueva gramática las producciones son de la forma $\alpha\rightarrow\beta$, donde $\alpha\in V_2^*$, y bien $\beta\in V_2^*$ o bien $\beta\in T_2$, es decir, consta de un único símbolo terminal. Además, la gramática G2 es del mismo tipo que la gramática G1.

En efecto, dada $G_1=\left(V_1,T_1, P_1,s_{01}\right)$, para cada símbolo terminal $t\in T_1$, sea vt un nuevo símbolo variable. Hagamos $V_2=V_1\cup \{v_t\vert t\in T_1\}$, s02=s01 y en el conjunto de produciones P2 colocamos cada una de las producciones en P1, habiendo sutituído toda aparición de caracteres $t\in T_1$ por sus respectivos $v_t\in V_2$, más las producciones de la forma $v_t\rightarrow t$. Por un lado, G1 está subsumida por G2 pues toda derivación en G1 da una derivación en G2 y, por otro lado, de la observación (2.3.1) se sigue que G2 está subsumida por G1. Es claro que la gramática G2 es del mismo tipo que G1.
next up previous contents
Siguiente: Ejercicios Un nivel arriba: Gramáticas formales Anterior: Ejemplos
Guillermo Morales-Luna
2000-06-27