IntroduccinGramticas libres
Gramticas sin Producciones Simples
Hacia las Gramticas PropiasGramticas sin Ciclos
Universidad de Cantabria
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Esquema
1 Introduccin
2 Gramticas libres
3 Gramticas sin Producciones Simples
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Introduccin
Las gramticas libres de contexto pueden presentar diferentesproblemas. Ya hemos visto como eliminar los smbolos intilesque tiene una gramtica.Veamos como transformar una gramtica para que no tengaciclos.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Cosas que Evitar
Las gramticas presentan ciclos porque:Hay producciones de la forma A 7 B.Hay producciones de la forma A 7 .
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Cosas que Evitar
Las gramticas presentan ciclos porque:Hay producciones de la forma A 7 B.Hay producciones de la forma A 7 .
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Cosas que Evitar
Claramente, no siempre es posible quitar todas lasproducciones del tipo A 7 , ya que siempre deber haber almenos una si el lenguaje contiene a la palabra vaca.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Eliminacin de producciones
DefinicinSea G = (V ,,Q0,P) una gramtica libre de contexto.
1 Llamaremos producciones en G a todas lasproducciones de la forma X 7 , donde X V es unsmbolo no terminal.
2 Diremos que la gramtica G es libre si verifica una delas dos propiedades siguientes:
O bien no posee producciones,o bien la nica produccin es de la forma Q0 7 y Q0no aparece en el lado derecho de ninguna otra produccinde P (es decir, no existe ninguna produccin de la formaX 7 Q0, con , (V )).
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Eliminacin de producciones
DefinicinSea G = (V ,,Q0,P) una gramtica libre de contexto.
1 Llamaremos producciones en G a todas lasproducciones de la forma X 7 , donde X V es unsmbolo no terminal.
2 Diremos que la gramtica G es libre si verifica una delas dos propiedades siguientes:
O bien no posee producciones,o bien la nica produccin es de la forma Q0 7 y Q0no aparece en el lado derecho de ninguna otra produccinde P (es decir, no existe ninguna produccin de la formaX 7 Q0, con , (V )).
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Ejemplo de Gramtica
EjemploConsideremos la gramtica cuyas producciones son:
Q0 7 aQ0bQ0 | bQ0aQ0 | .
No es una gramtica libre.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Pregunta sobre las Gramticas
A la vista de este ejemplo y la definicin, se puede resolvercon un autmata cuando una gramtica es libre?
Las variables pueden definirse como qN , por lo tanto sepueden representar como expresiones regulares.Los elementos del alfabeto son representables porexpresiones regulares.Incluiremos 7 como un smbolo.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Resultado
Teorema (Transformacin a Gramtica libre)Toda gramtica libre de contexto es equivalente a unagramtica libre. Adems, dicha equivalencia es calculablealgortmicamente.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
El Grafo de las -producciones
Utilizaremos la idea que se utiliz para la eliminacin desmbolos intiles. Primero guardamos en un conjuntoV := {A V : A `G }.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Algoritmo
Calculamos ahora un nuevo sistema de producciones P pormedio de una serie de transformaciones, que se basansolamente en sustituciones. Al principio, consideramos que Pes el conjunto vacio.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Algoritmo
Consideremos todas las producciones de la forma siguiente:
A 7 0B11 Bkk ,
donde i ((V\V) ), Bi V y no todos los i soniguales a .Definamos
P := P {A 7 0X11 Xkk : Xi {Bi , }}.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Algoritmo
Consideremos todas las producciones de la forma siguiente:
A 7 B1 Bk ,
donde Bi V.Definamos:
P := P ({A 7 X1 Xk : Xi {Bi , }} \ {A 7 }) .
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Algoritmo
Aadimos todas las producciones que no sean del tipo de lasdos mencionadas anteriormente. Esto es, aquellas en las queen la parte derecha no aparezca ninguna variable de V y nosean producciones.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Algoritmo
Notar que no hemos introducido ninguna produccin a P.Finalmente, si Q0 V sea V := V {Q0}, con Q0 6 V . Yaadamos
P = P {Q0 7 Q0 | }.En otro caso, V = V .
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
ltimas Observaciones
Varios puntos para reflexionar:Tiene la nueva gramtica smbolos intiles?Siempre crece de tamao? puede ser ms pequeaque la inicial?Como cambian los rboles de derivacin de una palabra?
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Producciones Simples
Definicin (Producciones Simples o Unarias)Se llaman producciones simples (unarias) a las produccionesde una gramtica libre de contexto de la forma A 7 B, donde Ay B son smbolos no terminales.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Resultado
Teorema (Eliminacin de Producciones Simples)Toda gramtica libre es equivalente a una gramtica sinproducciones simples. Esta equivalencia es calculablealgortmicamente.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Algoritmo
El algoritmo tiene dos partes. La primera parte sigue el mismoesquema algortmico usado en resultados anteriores. Lasegunda parte se dedica a eliminar todas las produccionessimples.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Clausura Transitiva
Clausura Transitiva de smbolos no terminales. Se trata decalcular, para cada A V , el conjunto siguiente:
VA := {B V : A `G B} {A}.
A partir de aqu, el algoritmo seguir derroteros muy similares.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Algoritmo
Entrada: Una gramtica libre de contexto G := (V ,,Q0,P)Para cada A V calcularMA := NA := {A}
mientras NA 6= M hacerM := NANA := {C V : B 7 C est en P, y B NA} NA
fin hacerSalida: Para cada A V , NA.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
Algoritmo
Eliminar las producciones simples. Para cada variable B tal queexiste una produccin simple A 7 B en P, procederemos somosigue:
Hallar todos los X s tales que B VX .Para cada produccin B 7 que no sea produccinsimple, aadir a P la produccin X 7 .Eliminar toda produccin del tipo X 7 B.
Gramticas Propias
IntroduccinGramticas libres
Gramticas sin Producciones Simples
ltimas Observaciones
Varios puntos para reflexionar:Tiene la nueva gramtica smbolos intiles?Es necesario que la gramtica sea libre para que elalgoritmo funcione?Despus de aplicar el algoritmo sigue siendo lagramtica libre?Como cambian los rboles de derivacin de una palabra?
Gramticas Propias
IntroduccinGramticas -libresGramticas sin Producciones Simples