Lenguajes de contexto

Introducción
El presente reporte de practica muestra una teoría resumida acerca de los lenguajes de contexto y
varios ejemplos que explica como resolverlos así como un grupo de ejercicios propuestos por el
alumno.
1. El estudiante revisará la teoría acerca de los Lenguajes Independientes de Contexto.
2. El estudiante realizará ejercicios de definición de GICs.
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 lenguajeformal es libre de contexto si hay una
gramática libre de contexto 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 deeficientes algoritmos de análisis sintáctico que, para una cadena de 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.
Definición formal
Así como cualquier gramática formal, unagramática libre de contexto puede ser definida mediante
la 4-tupla:
donde
• es un conjunto finito de terminales
• es un conjunto finito de no terminales
• es un conjunto finito de producciones
• el denominado Símbolo Inicial
• los elementos de son de la forma
Ejemplos
Ejemplo 1
Una simple gramática libre de contexto es
S → aSb | ε
donde | es un o lógico y es usado para separar múltiplesopciones para el mismo no terminal, ε
indica una cadena vacía. Esta gramática genera el lenguaje no regular .
Ejemplo 2
Aquí hay una gramática libre de contexto para expresiones enteras algebraicas sintácticamente
correctas sobre las variables x, y y z:
S → x | y | z | S + S | S - S | S *S | S/S | (S)
Generaría, por ejemplo, la cadena (x + y) *x - z *y / (x + x)
Ejemplo 3
Una gramáticalibre de contexto para un lenguaje consistente en todas las cadenas que se pueden
formar con las letras a y b, habiendo un número diferente de una que de otra, sería:
S → U | V
U → TaU | TaT
V → TbV | TbT
T → aTbT | bTaT | ε
T genera todas las cadenas con la misma cantidad de letras a que b, U genera todas las cadenas con
más letras a, y V todas las cadenas con más letras b.
Ejemplo 4
Otroejemplo para un lenguaje es . No es un lenguaje regular,
pero puede ser generado por la siguiente gramática libre de contexto.
S → aSc | B
B → bBc | ε
Propiedades de los lenguajes libres de contexto
• Una de las definiciones alternativas y equivalentes de lenguaje libre de contexto emplea
autómatas no deterministas: un lenguaje es libre de contexto si puede ser aceptado por ese
autómata.
•Un lenguaje puede ser también modelado como un conjunto de todas las secuencias de
terminales aceptadas por la gramática. Este modelo ayuda a entender las operaciones de
conjuntos sobre lenguajes.
• La unión y concatenación de dos lenguajes libres de contexto es también libre de contexto.
La intersección no tiene por que serlo.
• El inverso de un lenguaje libre de contexto es también libre decontexto, pero el
complemento no tiene por que serlo.
• Los lenguajes regulares son libres de contexto porque pueden ser descritos mediante una
gramática de libre contexto.
• La intersección de un lenguaje libre de contexto y un lenguaje regular es siempre libre de
contexto.
• Existen Gramáticas sensibles al contexto que no son libres de contexto.
• Para demostrar que un lenguaje dado no...