INDICE

TEMA 6.-GRAMATICAS LIBRES DE CONTEXTO

ARBOLES DE DERIVACION. AMBIGÜEDAD
SIMPLIFICACION DE LAS GRAMATICAS LIBRES DE CONTEXTO
ELIMINACION DE SIMBOLOS Y PRODUCCIONES INUTILES
PRODUCCIONES NULAS
PRODUCCIONES UNITARIAS
FORMAS NORMALES
  FORMA NORMAL DE CHOMSKY
  FORMA NORMAL DE GREIBACH



 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ARBOLES DE DERIVACION. AMBIGUEDAD

Consideremos una gramática G=(V,T,P,S) donde V={S}, T={a,b,c,f ,e ,(,),*,+} y las producciones son:
    S → abc,f ,e | (S+S) | (SS) | S*
Se trata de una gramática libre de contexto, ya que en la parte izquierda de las producciones solo aparece una variable.

Una derivación nos puede ayudar a determinar si una palabra pertenece a un determinado lenguaje y a determinar la estructura sintáctica de la misma, dicha estructura viene dada por el árbol de derivación (se construye a partir de la cadena de derivaciones).

Construcción del árbol de derivación:
 

Todos los nodos están etiquetados con un símbolo de la gramática.

La raíz esta etiquetada con el símbolo inicial.

Cada hoja etiquetada con un símbolo terminal o la cadena vacía (e).

Cada nodo interior esta etiquetado con un símbolo no terminal.

Si A es un símbolo no terminal, etiqueta de algún nodo interior y sus m hijos están etiquetados con X1X2...Xm, respectivamente, entonces A → X1X2...Xm es una producción de la gramática, y se añadiran tantos hijos como símbolos tenga la parte derecha de la producción (si la parte derecha es e , se añade un solo hijo etiquetado con e).
 

 Un árbol se dice completo cuando todas las etiquetas de los nodos hojas son símbolos terminales o bien la cadena vacía.

Aunque toda cadena de derivaciones lleva asociado un solo árbol este puede provenir de varias cadenas de derivaciones distintas. La existencia en una gramática de varias derivaciones para una misma palabra no produce ningún problema, siempre que de lugar al mismo árbol.

Otro problema que si puede ser grave es la ambigüedad y se produce si existen dos o mas árboles de derivación distintos para una misma palabra, ya que la gramática no va a determinar la estructura sintáctica de los elementos de la palabra ni como se agrupan los distintos elementos para formar la palabra completa.

Es suficiente que haya una palabra con 2 arboles de derivación distintos para que la gramática sea ambigua. El lenguaje generado por esta gramática no es inherentemente ambiguo, es decir, que existe otra gramática de tipo 2 o libre de contexto no ambigua y que genera el mismo lenguaje; aunque pueden existir gramáticas del tipo 2 que aunque genere el mismo lenguaje sigan siendo ambiguas.

EJEMPLO.-La siguiente gramática es ambigua:
    E → I | I-E | E-I 
    I → a | b | c | d
La palabra a-b-c admite dos arboles de derivación.

 
 

  Se obtienen dos arboles de derivación, por lo que la gramática es ambigua.

Dicha ambigüedad se podria eliminar quitando la producción E → I-E.
 
 
SIMPLIFICACION DE LAS GRAMATICAS LIBRES DE CONTEXTO
Para un mismo lenguajes de tipo 2 existen muchas gramáticas libres de contexto que lo generan, serán de formas muy diversas por lo que interesa simplificarlas lo mas posible y definir unas formas normales para las gramáticas que las hagan homogéneas.
 

ELIMINACION DE SIMBOLOS Y PRODUCCIONES INUTILES

Un símbolo X∈(V∪T) se dice útil si y solo si existe una cadena de derivaciones en G tal que S→*aXb →*w∈T* (si interviene en la derivación de alguna palabra del lenguaje generado por la gramática).

Una producción se dice útil si y solo si todos sus símbolos son útiles, es decir, podrá usarse en la derivación de alguna palabra del lenguaje asociado a la gramática.

Aunque se eliminen todos los símbolos y producciones inútiles el lenguaje generado por la gramática no cambiará.

ALGORITMO DE ELIMINACIÓN DE SÍMBOLOS Y PRODUCCIONES INUTILES.

1erpaso: Eliminar las variables desde las que no se puede llegar a una palabra de T* y las producciones en las que aparezcan.

 Sea  V' es un conjunto de variables.
    1.- V'=f .
    2.- Para cada producción de forma A→ w∈T*, A se introduce en V'.
    3.- Mientras V' cambie
      3.1- Para cada producción B→a
        3.1.1- Si todas las variables de a pertenecen a V', B se introduce en V'.
    4.- Eliminar las variables que estén en V y no en V'.
    5.- Eliminar todas las producciones donde aparezca una variable de la eliminadas en el paso anterior.
2º paso: Eliminar aquellos símbolos que no sean alcanzables desde el estado inicial, S, y las producciones en las que estos aparezcan.

V'' y J son conjuntos de variables.
J son las variables por analizar.
T' es un conjunto de símbolos terminales.
        1.- J={S}
        V''={S}
        T'=∅
        2.- Mientras J≠∅f
          2.1- Extraer un elemento de J, A (J=J-{A}).
          2.2- Para cada producción de la forma A→a .
            2.2.1- Para cada variable B en a .
              2.2.1.1- Si B no esta en V'' añadir B a J y a V''.
            2.2.2- Poner todos los símbolos terminales de a en T'.
        3.- Eliminar todas las variables que no estén en V'' y todos los símbolos terminales que no estén en T'.
        4.- Eliminar todas las producciones donde aparezca un símbolo o variable de los eliminados en el paso anterior.
EJEMPLO.- Eliminar símbolos y producciones inútiles de la siguiente gramática:
    S → gAe | aYB | cY U → kW
    A → bBY | ooC V → baXXX | oV
    B → dd | D W → c
    C → jVB | gi  X → fV,
    D → n Y → Yhm
Solución:
Decimos que el lenguaje generado por una gramática es vacío,si y solo si, la variable S resulta inútil en el primer paso del algoritmo entonces  se podran eliminar directamente todas las producciones pero no el símbolo S.

PRODUCCIONES NULAS
 

Estas producciones son de la forma A→e . Se va a tratar de eliminarlas sin que cambie el lenguaje generado por la gramática ni la estructura de los arboles de derivación.

Evidentemente si e∈ L(G) no vamos a poder eliminarlas todas sin que la palabra nula deje de generarse.

ALGORITMO DE ELIMINACIÓN DE PRODUCCIONES NULAS.

Dada una gramática G, construimos  una gramática G' equivalente sin producciones nulas y tal que L(G')=L(G)-{ε }, es decir, en esta nueva gramática no se genere la palabra nula.

1erpaso del algoritmo:

H es el conjunto de las variables anulables.
      1.- H=∅
      2.- Para cada producción A→&epsilon , se hace H=H∪ {A}.
      3.- Mientras H cambie
        3.1.- Para cada producción B→ A1A2...An donde Ai∈H se añade B a H.
2º paso del algoritmo:
      1.- Se eliminan todas las producciones nulas de la gramática
   
 
 2.- Para cada producción de la gramática de la forma A→a1a2...an
2.1- Se elimina la producción A→a1a 2...an
2.2- Se añaden todas las producciones de la forma 

A→b1b2...bn donde bi=ai siai∉H.
(bi=ai)∨ (bi=ε ) si ai∈H donde no todos los bi puedan ser nulos al mismo tiempo.

G' es la gramática resultante después de aplicar el algoritmo.

Si G generaba inicialmente la palabra nula, a partir de G', podemos construir una gramática G'' con una sola producción nula y que genera el mismo lenguaje que G, para ello se añade una nueva variable, S', que pasa a ser el símbolo inicial de la nueva gramática, G''. También se añaden dos producciones:
    S'→ S y S'→ε
EJEMPLO.- Eliminar las producciones nulas de la siguiente gramática:
      S → ABb | ABC
      C → abC | AB
      B → bB | ε
      A → aA | ε
Solución:

 


  PRODUCCIONES UNITARIAS

Estas producciones son de la forma A→B donde A,B∈V.

ALGORITMO.- TRANSFORMAR UNA GRAMÁTICA SIN PRODUCCIONES NULAS A UNA GRAMÁTICA SIN PRODUCCIONES UNITARIAS.

 Transformar una gramática G, en la que no se encuentra la producción nula, en otra equivalente G' en la que no existan producciones unitarias.

Sea  H el conjunto de parejas (A,B) tal que B se puede derivar a partir de A: A→B.

Pasos a seguir:
      1.- H=f
      2.- Para toda producción de la forma A→B, la pareja (A,B) se introduce en H.
      3.- Mientras H cambie
3.1- Para cada dos parejas (A,B),(B,C)
3.1.1- Si la pareja (A,C) no esta en H se introduce en H (A,C).
      4.- Se eliminan las producciones unitarias.
      5.- Para cada producción A→a
5.1- Para cada pareja (B,A)∈ H
5.1.1- Se añade una producción B→a
EJEMPLO.-Eliminar las producciones unitarias de la gramática:
      S → ABb | Ab | Bb| ABC | AB | AC | BC | A | B | C
      C → abC | ab | AB | A | B
      B → bB | b
      A → aA | a
Solución:


 
  FORMAS NORMALES
  FORMA NORMAL DE CHOMSKY

Una gramática de tipo 2 se dice que está en forma de Chomsky si y solo si todas las producciones tienen la forma:
  A → BC | a  donde A,B,C∈V, a∈T.

 
  ALGORITMO.- CALCULAR LA FORMA DE CHOMSKY DE UNA GRAMÁTICA.

Para que una gramática se pueda poner en esta forma lo primero que hay que hacer es suprimir las producciones nulas y unitarias. Seguidamente se aplican los siguientes pasos:
      1.- Para cada producción de la forma A→a1...anan∈(V∪T).
1.1.- Para cada ai,si ai es terminal: ai= a∈T.
1.1.1.- Se añade la producción Ca→ a.
1.1.2.-Se cambia ai por Ca en A→a1...an 
      2.- Para cada producción de la forma A→ B1...Bn, m>=3.
2.1.- Se añaden (m-2) variables D1D2...Dm-2 (distintas para cada producción).
2.2.- La producción A→ B1...Bm se reemplaza por A→ B1D1; D1→ B2D2; ... ; Dm-2→ Bm-1Bm
EJEMPLO.- La gramática ({S,A,B},{a,b},P,S) dada por las producciones:
      S → bA | aB
      A → bAA | AS | a
      B → aBB | bS | b
Pasarla a la forma normal de Chomsky.

Solución:


 
  FORMA NORMAL DE GREIBACH

Se dice que esta en forma normal de Greiback si y solo si todas las producciones tienen la forma
    A→ aa   donde a∈T, a∈(V∪T)*
 
ALGORITMO.-CALCULAR LA FORMA NORMAL DE GREIBACH DE UNA GRAMÁTICA.

Para que una gramática se pueda poner en esta forma se debe partir de una gramática en forma normal de Chomsky.

Suponemos que el conjunto de variables inicial de la gramática esta numerado V={A1,...,Am}.

1.- Modificar la gramática para que se verifique lo siguiente: si Ai→Aja es una producción de la gramática entonces j>i.

 
      1.- Para cada k=1,..,m
1.1.- Para cada j=1,..,k-1
1.1.1- Para cada producción Ak→Aja
1.1.1.1- Para cada producción Aj→b
1.1.1.1.1.Añadir Ak→b a
1.1.1.2- Eliminar Ak→Aja
1.2.- Si existe alguna producción de la forma Ak→Aka
1.2.1- Añadir una variable Bk.
1.2.2- Para cada producción de la forma Ak→Aka
1.2.2.1- Añadir Bk→ay Bk→a Bk
1.2.2.2- Eliminar Ak→Aka
1.2.3- Para cada producción de la forma Ak→ b , dondeb no empieza por Ak.
1.2.3.1- Añadir la producción Ak→ b Bk
Al final del algoritmo, todas las producciones tienen la forma:
        1.- Ai →Ajg,ji
        2.- Ai →ag , a∈ T
        3.- Bi →g , g ∈ (V∪ {B1,..,Bi-1})*
2.- Eliminar la recursividad por la izquierda  siguiendo los pasos del algoritmo siguiente:
      1.- Para cada i=m-1,..,1
1.1.- Para cada producción de la forma Ai→Ajg, ji
1.1.1.- Para cada producción Aj→a
1.1.1.1.- Añadir Ai→ag
1.1.2.- Eliminar Ai→Aja
      2.- Para cada i=1,2,..,m
2.1.- Para cada producción de la forma Bi→Ajg
2.1.1.- Para cada producción Aj→a
2.1.1.1.- Añadir Ai→a g
2.1.2.- Eliminar Bi→Ajg
El resultado de este segundo paso es una gramática en forma normal de Greibach.

EJEMPLO.- Realizar una Normalización en Greibach de la siguiente gramática:
      S1→ S1S2c | S3bS3
      S2 →S1S1,d
      S3 →S2e
Solución: