Libre contexto

Universidad San Carlos de Guatemala.
Facultad de ingeniería.
Escuela de Ciencias y Sistemas.
Lenguajes Formales de Programación.
Sección A-.
Ing. Damaris Campos.






Gramáticas Libres de Contexto.




Grupo 6:
Douglas Ordóñez Simón 200819409.
Guillermo René Medinilla 201213233.
Marvin Emmanuel Pivaral 201213587.
Eiji Arturo De PazPérez 201213623.
Octubre de 2013.


INTRODUCCIÓN
Las gramáticas libres de contexto (GLC) permiten definir un lenguaje mediante reglas que nos permiten generar o producir cadenas del lenguaje, estas gramáticas son similares a las gramáticas de los lenguajes naturales, pero mucho más restrictivas y sencillas.
Un ejemplo de regla de una gramática: Oración, Sujeto, Predicado.
Estas reglas sesuelen llamar reglas de reescritura: el símbolo Oración se puede reescribir por el símbolo Sujeto seguido del símbolo Predicado.
Al igual que con los lenguajes regulares podemos definir un autómata como una máquina reconocedora de cadenas (palabras) de un determinado lenguaje.
Los autómatas con los que trabajaremos en este tema son algo más complejos que los AF.

GRAMATICAS LIBRE DE CONTEXTOJerarquía de Noam Chomsky



Gramáticas Generativas
Una gramática generativa es una cuádrupla (V, T, P, S) en la que:
V es un conjunto de no terminales. Representado por letras mayúsculas
T el alfabeto, conjunto de terminales. Representado por letras minúsculas
P conjunto de pares (α,β), llamados reglas de producción. α,β en (V unión T)*. Contiene, α al menos un símbolo de V.Representado α→β.
S es un elemento de V, llamado símbolo de partida.
Pasos de Derivación
Dada la gramática G = (V, T, P, S) y dos palabras α, β en (V unión T)* β es derivable a partir de α en un paso (α→β) si y solo si existen palabras , en (V unión T)* y una producción γ→φ tales que:
α = y β = . La derivación seria:
→
Secuencia de Derivación
Secuencia [1 a n], n>0, de pasos de derivación β esderivable de α (α→*β) si y solo si existe una secuencia de palabras ,…, (n >= 1) tales que:
α→ →→…→→β
Lenguaje Generado
Se define como lenguaje generado por una gramática G = (V, T, P, S) al conjunto e cadenas formadas por símbolos terminales en V y que son derivables a partir del símbolo de partida S. Es decir: L(G) = {W|W EN T* y S→*W}
Gramática libre de Contexto
Conocidas también comogramáticas de tipo 2 o gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes del contexto, son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico.
Como toda gramática se definen mediante una cuádrupla G = {N, T, P, S} siendo:
N conjunto finito de símbolos no terminales.
T conjunto finito de símbolos terminales
Pconjunto finito de producciones
S símbolo distinguido o axioma
S no pertenece a (N unión T)
N intersección T = vacío
En una gramática libre de contexto, cada producción de P tiene la forma
Α→ω

Es decir, que en el lado izquierdo de una producción pueden aparecer el símbolo distinguido o un símbolo no terminal y en el lado derecho de una producción cualquier cadena de símbolos terminales y/ono terminales de longitud mayor o igual que 1.
La gramática puede contener también producciones si el lenguaje lo permite.
Árbol de Derivación
El árbol de derivación, al representar las producciones utilizadas para generar una palabra, está indicando además su estructura, lo que resulta determinante para entender su significado. Por esa razón, en los mecanismos para reconocer lenguajesindependientes del contexto no es suficiente con indicar si una cadena determinada pertenece o no al lenguaje, también es muy importante que el reconocedor construya el árbol de derivación de dicha cadena.
Notación BNF
La notación de Backus-Naur, también conocida por sus denominaciones inglesas Backus-Naur form (BNF), Backus-Naur formalism o Backus normal form, es un metalenguaje usado para expresar...