Lenguajes y Automatas



Lenguajes y Autómatas

Ingeniería en Computación

Formas gramaticales tipo Backusnaur. BNF

Gramática Formal.

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ógicamatemática, las ciencias de la computación y la lingüística teórica, frecuentemente con métodos e intereses divergentes.
En un lenguaje formal, a las cadenas formadas según las reglas de la gramática formal se las llama fórmulas bien formadas, y el conjunto de todas las fórmulas bien formadas constituye un lenguaje formal. Una gramática formal no describe el significado de las fórmulas bien formadas, sinosolamente su forma. La teoría de los lenguajes formales estudia las gramáticas formales y los lenguajes formales, y es una rama de la matemática aplicada. Sus aplicaciones se encuentran en la ciencia computacional teórica, la lingüística, la semántica formal, la lógica matemática y otras áreas.
Introducción
Una gramática formal es un conjunto de reglas para reescribir cadenas de caracteres,junto con un símbolo inicial desde el cual debe comenzar la reescritura. Por lo tanto, una gramática formal generalmente se piensa como una generadora de lenguajes. Sin embargo, a veces también puede ser usada como la base para un "reconocedor": una función que determina si una cadena cualquiera pertenece a un lenguaje o es gramaticalmente incorrecta.
Hay distintos tipos de gramáticas formales quegeneran lenguajes formales. Imaginemos una gramática con estas dos reglas:
1. A → bA
2. A → c
El elemento en mayúsculas es el símbolo inicial. Los elementos en minúsculas son los símbolos terminales. Para generar cadenas de caracteres, la idea es sustituir el símbolo inicial de la izquierda por los símbolos de la derecha, y luego repetir el proceso hasta que sólo haya símbolos terminales. Porejemplo:
A → bA → bbA → bbbA → bbbc
Esta gramática da lugar a un lenguaje formal que consiste en el conjunto de todas las cadenas de caracteres que pueden ser generadas por medio ellas. Por ejemplo: bbbc, bbbbbbbbc, c, bc, etc.
Para comprender mejor la idea, podemos considerar un modelo de reescritura para el español:
1. O → SUJ PRED (Oración → Sujeto Predicado)
2. SUJ → Det N (Sujeto →Determinante Nombre)
3. PRED → V COMP (Predicado → Verbo Complemento)
4. Det → el
5. N → niño, (hombre, anciano)
6. V → duerme, (ríe, come)
7. COMP → plácidamente, (intranquilo)
Estas reglas pueden utilizarse para generar la frase "el niño duerme plácidamente", así:
1. O (símbolo inicial)
2. SUJ(ETO) PRED(ICADO) (por la regla 1)
3. Det(erminante) N(OMBRE) PRED(ICADO) (por la regla 2)
4.Det(erminante) N(OMBRE) V(ERBO) COMP(LEMENTO) (por la regla 3)
5. el N(OMBRE) V(ERBO) COMP(LEMENTO) (por la regla 4)
6. el niño V(ERBO) COMP(LEMENTO) (por la regla 5)
7. el niño duerme COMP(LEMENTO) (por la regla 6)
8. el niño duerme plácidamente (por la regla 7)
Vemos que existen unas definiciones especiales como FRASE, SUJETO, etc. que no aparecen en la frase final formada. Son unas entidadesabstractas denominadas "categorías sintácticas" que no son utilizables en una oración (tienen un papel similar al de las categorías gramaticales de las lenguas naturales). E igualmente el mismo sistema permite derivar otras oraciones similares usando formas las formas léxicas entre paréntesis:


Det
N
V
COMP
El
niño
hombre
anciano
duerme
ríe
come
plácidamente
intranquilo

Lascategorías sintácticas definen la estructura del lenguaje representando porciones más o menos grandes de las frases. Existe una jerarquía interna entre las categorías sintácticas.
La categoría superior sería la FRASE que representa una oración válida en lengua castellana.
Por debajo de ella se encuentran sus componentes. Ninguna de estas categorías dan lugar a frases válidas solo la categoría...