Definición de gramática

Las gramáticas están formadas por 4 componentes:

• Conjunto finito de símbolos no terminales $V$ o variables, que permiten representar subconjuntos del lenguaje o estados intermedios en la generación de palabras.
• El alfabeto de símbolos terminales $T$, que son los símbolos finales del lenguaje.
• El símbolo inicial o axioma $S$ de la gramática es una de las variables a partir del cual se obtiene cualquier palabra del lenguaje.
• Un conjunto finito de producciones o reglas $P$ que indican las transformaciones posibles desde los símbolos no terminales a las palabras del lenguaje.
  • Una variable o cabeza de producción
  • El **símbolo de producción $\to$.
  • Una cadena de 0 o más símbolos terminales y no terminales, que son el cuerpo de la producción.

Las letras mayúsculas normalmente denotan variables y las minúsculas símbolos terminales.

Tipos de gramáticas

Ya que tenemos el contexto de lo que es una gramática, y expandiendo lo que se vio en la introducción, diferenciamos varios tipos de gramáticas en función de las restricciones que tenemos a la hora de crear las reglas de producción.

• G0 o Tipo 0: gramáticas sin restricciones (GSR) $$ \alpha \to \beta \\ \alpha \in (V + T)^+ \\ \beta \in (V + T)^* $$
• G1 o Tipo 1: gramáticas sensibles al contexto (GSC) $$ \begin{align*} \alpha \to& \; \beta \\ |\alpha| \le& \; |\beta| \\ \alpha = z_1 A z_2 &\quad A \in V \\ \beta = z_1 \gamma z_2 &\quad \gamma \in (V + T)^+ \\ z_1, z_2 \in T^* &\\ \end{align*} $$
• G2 o Tipo 2: gramáticas independientes del contexto (GIC) $$ A \to \beta \\ A \in V \\ \beta \in (V + T)^* $$
• G3 o Tipo 3: gramáticas regulares $$ A \to \beta \\ A \in V \\ \beta \in \begin{cases} aB & a \in T^+ \\ Ba & B \in V \\ b & b \in T^* \\ \end{cases} \\ $$

Por tanto:

Gramáticas Regulares (GR)

Los lenguajes regulares pueden asociarse a una gramática de tipo 3 o regular. Por la definición del apartado anterior, tenemos que son:

• Lineales por la derecha (solo variables por la derecha)
• Lineales por la izquierda (solo variables por la izquierda)

Gramáticas independientes de contexto (GIC)

En cambio, las reglas de las Gramáticas Independientes de Contexto tienen la siguiente forma:

Es decir,

• La cabeza de producción siempre es una variable
• El cuerpo de producción pueden ser variables o símbolos terminales (incluyendo $\lambda$)

Gramáticas sensibles al contexto (GSC)

Un lenguaje $L$ es sensible al contexto (LSC) si existe una GSC tal que $L = L(G)$ o $L = L(G) \cup \set{\lambda}$.

Los LSC que no contengan $\lambda$ son reconocidos por los Autómatas Linealmente Acotados (ALA).

Gramáticas sin restricciones (GSR)

Las GSR generan los LRE.

Análisis de una gramática

Derivaciones de una gramática

Sea $G = (V, T, P, S)$ y $\alpha A \beta$ una cadena de terminales y variables, donde $A$ es variable ($A \in V$) y el resto son variables y terminales ($\alpha, \beta \in (V + T)^*$).

Si existe la producción $A \to \gamma$, entonces:

La implicación sobre la gramática $G$ indica que se utilizan sus reglas de producción para derivar la nueva expresión. Alternativamente, $\overset{*}{\underset{G}{\implies}}$ denota un conjunto de derivaciones (no solo una).

Básicamente consisten en expandir las reglas de la gramáticas para llegar a una cadena del lenguaje que define.

Lenguaje de una gramática

Es decir, cualquier cadena formada por la gramática desde el axioma es una forma sentencial.

Es decir, cualquier cadena de símbolos terminales derivada del axioma es una sentencia. El lenguaje de la gramática es el conjunto de todas estas sentencias.

Árbol de derivación

Se pueden representar las derivaciones de la gramática en forma de árbol.

• El nodo raíz es el símbolo axioma.
• Cada nodo interior está etiquetado como una variable.
• Cada nodo hoja está etiquetada con un símbolo terminal o $\lambda$. Si es $\lambda$, no debe tener hermanos.
• Si un nodo interior etiquetado como $A$ tiene los hijos por este orden $X_1, \ldots, X_k$, entonces $A \to X_1, \ldots, X_k$ es una producción de la gramática.

Concatenando todas las hojas del árbol de izquierda a derecha, se obtiene la cadena resultado, que se deriva desde la raíz.

Para el ejemplo antes visto: $E \overset{*}{\implies} ‘a * (a + b00)'$

    flowchart TB
    1((E)) --> 2((E))
    1 --> 3((*))
    1 --> 4((E))
    2 --> 5((I)) --> 6((a))
    4 --> 7(("("))
    4 --> 8(("E"))
    4 --> 9((")"))
    8 --> 10((E))
    8 --> 11((+))
    8 --> 12((E))
    10 --> 13((I)) --> 14((a))
    12 --> 15((I))
    15 --> 16((I))
    15 --> 17((0))
    16 --> 18((I)) --> 20((b))
    16 --> 19((0))

Ambigüedad

La existencia de derivaciones diferentes no supone un problema para la gramática, pero la existencia de varios árboles de derivación diferentes sí.

Estas ambigüedades no están permitidas en los lenguajes formales. No entraremos en mucho detalle, pero es importante tenerla en cuenta.

Formas normales para GIC

Veremos las siguientes formas normales:

• Forma normal de Chomsky
• Forma normal de Greibach

El principal motivo para usar las formas normales es que no cambian la gramática y reducen la complejidad para la obtención de sus derivaciones, es más fácil de aplicar. Para comprobar determinada GIC en un computador, se tendrán que comprobar todas las reglas para cada símbolo, lo que es un alto coste computacional. Las formas normales son alternativas que intentan arreglar eso.

En general, antes de obtener una gramática en forma normal, es necesario realizar unas transformaciones previas que no modifican el lenguaje generado:

1. Eliminación de producciones con $\lambda$
2. Eliminación de producciones unitarias (reglas de encadenamiento de la forma $A \to B, \enspace A,B \in V$)
3. Eliminación de símbolos inútiles
   1. Eliminar símbolos no generadores
   2. Eliminar símbolos no alcanzables

Eliminación de producciones con $\lambda$

Algoritmo para encontrar todos los símbolos anulables:

• Paso base: si existe una producción $A \to \lambda$, $A$ es anulable.
• Paso inductivo: si existe una producción $A \to C_1 \ldots C_k$, en las que todas las $C_i$ son anulables, entonces $A$ es anulable.

Eliminación de producciones unitarias

Son importantes eliminarlas porque no cambian nada (solo renombran variables) y añaden pasos extra en las derivaciones.

Obtención de los pares unitarios:

• Paso base: $(A, A)$ es un par unitario para toda variable $A$.
• Paso inductivo: sea $(A, B)$ un par unitario y $B \to C$ una producción donde $C$ es una variables. Entonces $(A, C)$ es un par unitario.

Eliminación de símbolos inútiles

Es decir, un símbolo es útil si la gramática lo utiliza para generar sentencias.

Es decir, un símbolo es generador cuando a partir de él puedo derivar sentencias; mientras que un símbolo alcanzables es aquel al que se puede llegar desde el axioma.

Algoritmo para calcular símbolos generadores:

• Paso base: todo símbolo terminal es generador.
• Paso inductivo: dada una producción $A \to \alpha$, donde $A$ es variable y $\alpha$ es generador; entonces $A$ también es generador. Se incluye el caso donde $\alpha = \lambda$.

Algoritmo para calcular símbolos alcanzables:

• Paso base: $S$ es alcanzable.
• Paso inductivo: para todas las producciones $A \to \alpha$, donde $A$ es alcanzable; entonces $\alpha$ también será alcanzable.

Una vez determinados los símbolos útiles, se eliminan los que no lo son.

Forma Normal de Chomsky (FNC)

Se dice que una gramática $G$ está en la Forma Normal de Chomsky (FNC) si todas sus producciones tienen la forma:

Características:

• Un cadena de longitud $n$ se analiza en $2n - 1$ pasos.
• El árbol de derivación es binario y su profundidad máxima es $n$.
• Se usa como algoritmo el método CYK.

Para convertir una gramática a FNC:

1. Eliminar las producciones con $\lambda$, las producciones unitarias y símbolos inútiles.

2. Luego, conseguir que en los cuerpos de longitud 2 o más solo aparezcan 2 variables.

   1. Para cada símbolo terminal $a$ que aparece en un cuerpo de longitud 2 o más, se crea una nueva variable $A$.
   2. $A$ solo tiene la producción $A \to a$.
   3. Se sustituyen las apariciones de $a$ por $A$

3. Descomponer los cuerpos de longitud 3 o más en una cascada de producciones en cuyos cuerpos sólo aparezcan 2 variables.

   1. Se descomponen las producciones de forma $A \to B_1 \ldots B_k$ para $k \ge 3$, con un grupo de variables en cada cuerpo.
   2. Se introducen $k - 2$ variables nuevas: $C_1, \ldots C_{k-2}$.
   3. Se reemplaza la producción original por las $k - 1$ producciones:
      • $A \to B_1 C_1$
      • $C_1 = B_2 C_2$
      • …
      • $C_{k-3} \to B_{k-2} C_{k-2}$
      • $C_{k-2} \to B_{k-1} B_{k}$

Forma Normal de Greibach

Todo LIC no vacío es $L(G)$ para alguna gramática $G$ cuyas producciones tienen la forma:

donde $a$ es un símbolo terminal y $\alpha$ es una cadena de 0 o más variables.

El uso de una producción introduce un símbolo terminal en una forma sentencial.

• Una cadena de longitud $n$ tiene una derivación de $n$.
• Una analizador sintáctico descendente parará a profundidad $n$.
• Nunca habrá recursividad por la izquierda.

==> Es más eficiente que Chomsky, pero tiene la misma complejidad (lineal).