Proyecto finaldocx

TECNOLOGICO DE ESTUDIOS SUPERIORES DE ECATEPEC
DIVISIÓN DE INGENIERIA EN SISTEMAS COMPUTACIONALES
LENGUAJES Y AUTOMATAS 1

PROYECTO FINAL
INTEGRANTES:
ACEVEDO VISUET NAYELI
GARCIA MORALES JULIO CESAR
MAYA RANGEL ROSALBA
SANCHEZ LOVATO JOSE ALBERTO


PROFESORA:
XOCHITL RAUQUEL WONG COHEN

GRUPO:
5501

FECHA DE ENTREGA:
22-06-15

INTRODUCCION

El diseño de gramáticas libres del contexto no estrivial, más si tenemos la restricción de que no haya producciones— o producciones unitarias (.1 —• B). Deseamos, al igual que con los lenguajes regulares, disfrutar de una cierta libertad de diseño, para después depurar la gramática y dejarla de acuerdo a todas las reglas. Simplemente exigiremos que del lado izquierdo haya un único símbolo no terminal y del lado derecho una cadena arbitraria en A'U T) m. al fin que ya vimos que cualquier gramática que cumple con esto puede ser transformada en una donde las producciones tengan la forma canónica que dimos antes.

Dimos algunas sugerencias respecto a cómo construir autómatas finitos para determinados lenguajes. En esta sección intentaremos presentar cómo enfrentar el reto de construir una gramática libre del contexto para un lenguaje libredel contexto.


















INDICE
INTRODUCCION 2
INDICE 3
GRAMÁTICA LIBRE DE CONTEXTO 4
DERIVACIONES Y ÁRBOLES SINTÁCTICOS 5
FORMAS NORMALES 7
PROBLEMAS INDECIDIBLES 7
PROPIEDADES DE LOS LENGUAJES LIBRES DE CONTEXTO 8
DESARROLLO 8
APLICACIONES 18
CONCLUSIONES 20
REFERENCIAS 21


GRAMÁTICA LIBRE DE CONTEXTO

En lingüística e informática, una gramática libre de contexto (o de contexto libre)es una gramática formal en la que cada regla de producción es de la forma:

V → w

Donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre decontexto que lo genera.

Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la sintaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadenade caracteres dada determinen cómo puede ser generada desde la gramática. Los analizadores LL y LR tratan restringidos subconjuntos de gramáticas libres de contexto.
La notación más frecuentemente utilizada para expresar gramáticas libres de contexto es la forma Backus-Naur.

Así como cualquier gramática formal, una gramática libre de contexto puede ser definida mediante la 4-tupla:

G=(V_t, V_n,P, S) donde

Vt es un conjunto finito de terminales
Vn es un conjunto finito de no terminales
P es un conjunto finito de producciones
S € Vn el denominado Símbolo Inicial
Los elementos de P son de la forma
V_n \longrightarrow (Vt U Vn)*
DERIVACIONES Y ÁRBOLES SINTÁCTICOS

Existen básicamente dos formas de describir cómo en una cierta gramática una cadena puede ser derivadadesde el símbolo inicial. La forma más simple es listar las cadenas de símbolos consecutivas, comenzando por el símbolo inicial y finalizando con la cadena y las reglas que han sido aplicadas. Si introducimos estrategias como reemplazar siempre el no terminal de más a la izquierda primero, entonces la lista de reglas aplicadas es suficiente. A esto se le llama derivación por la izquierda. Porejemplo, si tomamos la siguiente gramática:

(1) S → S + S
(2) S → 1

Y la cadena "1 + 1 + 1", su derivación a la izquierda está en la lista [(1) (1) (2) (2) (2)]. Análogamente, la derivación por la derecha se define como la lista que obtenemos si siempre reemplazamos primero el no terminal de más a la derecha. En ese caso, la lista de reglas aplicadas para la derivación de la cadena con la...