Matematicas Discretas

Gramática libre de contexto
De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
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 hechode 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 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 síntaxis de la mayoría de lenguajes de programación está definida mediante gramáticaslibres 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 cadena de caracteres dada determinen como 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 expresargramáticas libres de contexto es la forma Backus-Naur.
Contenido[ocultar] * 1 Definición formal * 2 Ejemplos * 2.1 Ejemplo 1 * 2.2 Ejemplo 2 * 2.3 Ejemplo 3 * 2.4 Ejemplo 4 * 2.5 Otros ejemplos * 3 Derivaciones y árboles sintácticos * 4 Formas normales * 5 Problemas indecidibles * 6 Propiedades de los lenguajes libres de contexto * 7 Véase también |[editar] Definición formal
Así como cualquier gramática formal, una gramática libre de contexto puede ser definida mediante la 4-tupla:
G = (Vt,Vn,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
* el denominado Símbolo Inicial
* los elementos de P son de la forma

[editar] Ejemplos[editar] Ejemplo 1
Una simple gramática libre de contexto es
S → aSb | ε
donde | es un o lógico y es usado para separar múltiples opciones para el mismo no terminal, ε indica una cadena vacía. Esta gramática genera el lenguaje no regular .
[editar] 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)
[editar] Ejemplo 3
Una gramática libre 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 conla 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.
[editar] Ejemplo 4
Otro ejemplo 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 | ε
[editar] Otros ejemplos
Las gramáticas libres de contexto no están limitadas a lenguajesmatemáticos formales.
La gramática de Lojban, un lenguaje artificial hablado con gran capacidad expresiva, es también libre de contexto y no ambiguo.
El lingüista indio Pánini (siglo IV a. C.) describió el sánscrito usando una gramática libre de contexto en su texto Astadhiai.
Recientemente se ha sugerido que una clase de poesía tamil llamada Venpa utiliza principalmente una gramática libre decontexto.
[editar] Derivaciones y árboles sintácticos
Existen básicamente dos formas de describir cómo en una cierta gramática una cadena puede ser derivada desde 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...