Informatico

TEMA 8: GRAMÁTICAS LIBRES DEL CONTEXTO
José Miguel Puerta Antonio Fernández Caballero
Departamento de Informática Universidad de Castilla-la Mancha
Teoría de Autómatas y Lenguajes Formales 1

TEMA 8: GRAMÁTICAS LIBRES DEL CONTEXTO INDICE Introducción Conceptos sobre GLCs Limpieza de GLCs (a) Eliminación de símbolos y producciones inútiles (b) Eliminación de producciones nulas (c) Eliminaciónde producciones unitarias Formas normales (a) Forma normal de Chomsky (FNC) (b) Forma normal de Greibach (FNG)
Teoría de Autómatas y Lenguajes Formales 2

TEMA 8: GRAMÁTICAS LIBRES DEL CONTEXTO
INTRODUCCIÓN
Como sabemos, en una gramática libre de contexto (GLC) G = (N, T, P, S) las producciones tienen la siguiente forma: ⎧ A → β con A ∈ N , β ∈ (N ∪ T )+ ⎪ ⎨ ⎪S → ε ⎩ Las GLCs tienen unagran importancia en la definición de lenguajes de programación, interpretación del lenguaje natural, construcción de compiladores, etc ... Por comodidad a la hora de definir lenguajes, la definición anterior se extiende a la siguiente: A → β con A ∈ N , β ∈ (N ∪ T )* En este tema veremos que una GLC escrita de esta forma más general, siempre puede escribirse en la versión más restrictiva (sólo Spuede producir ε).
Teoría de Autómatas y Lenguajes Formales 3

TEMA 8: GRAMÁTICAS LIBRES DEL CONTEXTO CONCEPTOS SOBRE GLCs
Árbol de derivación Las derivaciones se pueden representar en forma de árbol Derivación más a la izquierda y más a la derecha Si existe un árbol de derivación con la raíz etiquetada con A y resultado w, entonces A ⇒* w, A ⇒mi* w, A ⇒md* w. Gramática ambigua Una sentencia w sedenomina ambigua si puede obtenerse por más de un árbol de derivación (o equivalentemente, más de una derivación más a la izquierda o más a la derecha). Una gramática G se denomina ambigua si el lenguaje que genera contiene alguna sentencia ambigua. Lenguaje inherentemente ambiguo Un lenguaje se denomina inherentemente ambiguo si no existe una gramática no ambigua que lo genere.
Teoría deAutómatas y Lenguajes Formales 4

TEMA 8: GRAMÁTICAS LIBRES DEL CONTEXTO Ejercicio Obtener la gramática que genera el lenguaje

L = a n b n c m d m | n, m ≥ 1 ∪ a n b m c m d n | n, m ≥ 1
y probar que es ambigua.

{

} {

}

Teoría de Autómatas y Lenguajes Formales

5

TEMA 8: GRAMÁTICAS LIBRES DEL CONTEXTO LIMPIEZA DE GLCs (1) El objetivo de esta parte del tema, es probar que dada unagramática G, siempre podemos encontrar otra gramática G’ equivalente y escrita de forma más correcta. En concreto, la nueva gramática no tendrá: Producciones inútiles Producciones nulas (excepto S → ε si ε ∈ L(G)) Producciones unitarias En algunos textos este proceso se denomina simplificación de GLCs, aunque como veremos sólo el primer paso "simplifica" realmente la gramática.
Teoría de Autómatasy Lenguajes Formales 6

TEMA 8: GRAMÁTICAS LIBRES DEL CONTEXTO LIMPIEZA DE GLCs (2) Eliminación de producciones inútiles (1) Un símbolo X ∈ (N ∪ T) es útil si aparece en una secuencia de derivaciones S ⇒* α1Xα2 ⇒* z ∈ T* Una producción se dice útil si y solo si todos sus símbolos son útiles. Esto es equivalente a que pueda usarse en la derivación de alguna palabra del lenguaje asociado a lagramática. Eliminando todos los símbolos y producciones inútiles el lenguaje generado por la gramática no cambia.
Teoría de Autómatas y Lenguajes Formales 7

TEMA 8: GRAMÁTICAS LIBRES DEL CONTEXTO LIMPIEZA DE GLCs (3) Eliminación de producciones inútiles (2) El algoritmo para eliminar los símbolos y producciones inútiles consta de dos pasos: 1.Símbolos no generativos: Eliminar los símbolos noterminales desde los que no se puede llegar a una palabra de T y las producciones en las que aparezcan. 2.Símbolos no accesibles: Eliminar aquellos símbolos que no sean alcanzables desde el símbolo inicial, S, y las producciones en las que aparecen.

Teoría de Autómatas y Lenguajes Formales

8

TEMA 8: GRAMÁTICAS LIBRES DEL CONTEXTO LIMPIEZA DE GLCs (4) Eliminación de producciones inútiles...