1. Que es una 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 de contexto que lo genera.
2. Algunas propiedades de los lenguajes libres de contexto son:
ü 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.
ü La unión y concatenación de dos lenguajes libres de contexto es también libre de contexto. La intersección no tiene por qué serlo.
3. Una gramática formal es:
Una estructura matemática con un conjunto de reglas de formación que definen las cadenas de caracteres admisibles en un determinado lenguaje formal o lengua natural. Las gramáticas formales aparecen en varios contextos diferentes: la lógica matemática, las ciencias de la computación y la lingüística teórica, frecuentemente con métodos e intereses divergentes.
4. Una gramática formal está en Forma normal de Chomsky :
Si todas sus reglas de producción son de alguna de las siguientes formas:
o α o donde
, 
y 
son símbolos no terminales (o variables) y α es un símbolo terminal. Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente.
5. Las 3 simplificaciones preliminares son para poder realizar la FNC son:
ü Eliminar símbolos inútiles
ü Eliminar producciones ε
ü Eliminar producciones unitarias
6. Después de realizar las 3 simplificaciones preliminares, los 2 pasos a transformar una gramática limpia a FNC son:
ü Organizar todos los cuerpos de longitud 2 o mayor para que consistan solo de variables.
ü Dividir cuerpos de longitud de 3 o mas en una cascada de producciones, cada una con un cuerpo formado por dos variables.
7. Requisito para transformar una gramática a FNG:
Que la gramática se haya transformado anterior mente a Forma Normal de Chomsky
8. Una gramática libre de contexto esta en forma normal de Greibach:
Si todas sus producciones son de la forma siguiente: A → αX
ü A es un simbolo no terminal.
ü α es un simbolo terminal.
ü X es una secuencia de terminales y no terminales, inclusive puede ser la palabra vacia.
9. Para que ayuda tener las gramáticas normalizadas:
El tener las gramáticas normalizadas ayudara a evitar ambigüedades, como generar palabras distintas si se realizan derivaciones por la izquierda o por la derecha, la cadena resultante tendría que ser la misma, la normalización busca evitar eso.
10. Que forma normal es mas importante:
La forma normal de Chomsky
Dudas:
1- Para que nos puede servir la forma Normal de Chomsky y Greibach?.
2- ¿Hasta qué profundidad deberíamos explorar el árbol de expansión para decidir si una cadena w de longitud n es generada o no por una gramática en FNC/FNG?
3- De que manera podemos aplicar la forma normal de chomsky y greibach?
4- Porque es importante el orden para descomponer un algoritmo en forma normal de chomsky?
5- Porque una gramatica que no genere una cadena vacia puede ser transformada en una equivalente?
Introduccion.
Forma normal de Chomsky
Simplificaciones preliminares
Pasos Finales
Formal Normal de Greibach
Algoritmo(Ejemplo)
Resumen
Algunas generalidades:
-A, B, C, D, E y S denotan variables, S es el símbolo inicial.
-a,b, c, d, e, dígitos, y cadenas en letras negrillas son terminales.
-X,Y, y Z denotan símbolos que pueden ser variables o terminales.
-u, v, w, x, y, z denotan cadenas terminales.
-Las letras griegas α, ß y ɣ, denotan cadenas de variables y terminales.
Descargar Diapositiva + trabajo + preguntas clic aqui
No hay comentarios:
Publicar un comentario