Gramtica formal
Esta imagen muestra la relacin entre lascadenas de caracteres,
lasfrmulas bien formadasy losteoremas. En algunossistemas formales,
sin embargo, el conjunto de los teoremas coincide con el de las
frmulas bien formadas.Unagramtica formales una estructura matemtica
con un conjunto de reglas de formacin que definen lascadenas de
caracteresadmisibles en un determinadolenguaje formalolengua
natural. Las gramticas formales aparecen en varios contextos
diferentes: lalgica matemtica, lasciencias de la computaciny
lalingsticaterica, frecuentemente con mtodos e intereses
divergentes.En un lenguaje formal, a las cadenas formadas segn las
reglas de la gramtica formal se las llamafrmulas bien formadas, y
el conjunto de todas las frmulas bien formadas constituye
unlenguaje formal. Una gramtica formal no describe elsignificadode
las frmulas bien formadas, sino solamente su forma. Lateora de los
lenguajes formalesestudia las gramticas formales y los lenguajes
formales, y es una rama de lamatemtica aplicada. Sus aplicaciones
se encuentran en laciencia computacional terica, lalingstica,
lasemntica formal, lalgica matemticay otras reas.ndice[ocultar]
1Introduccin 2Gramticas formales en lingstica terica 2.1Definicin
de una C-gramtica 2.2Definicin de una ES-gramtica 2.3Derivaciones
2.3.1Jerarqua de Chomsky 2.4Limitacin de las gramticas formales
3Gramticas formales en matemticas y lgica 4Vase tambin 5Referencia
5.1BibliografaIntroduccin[editar]Una gramtica formal es un conjunto
de reglas para reescribir cadenas de caracteres, junto con un
smbolo inicial desde el cual debe comenzar la reescritura. Por lo
tanto, una gramtica formal generalmente se piensa como una
generadora de lenguajes. Sin embargo, a veces tambin puede ser
usada como la base para un "reconocedor": una funcin que determina
si una cadena cualquiera pertenece a un lenguaje o es
gramaticalmente incorrecta.Hay distintos tipos de gramticas
formales que generan lenguajes formales (vase lajerarqua de
Chomsky). Imaginemos una gramtica con estas dos reglas:1. A bA2. A
cEl elemento en maysculas es elsmbolo inicial. Los elementos en
minsculas son lossmbolos terminales. Para generar cadenas de
caracteres, la idea es sustituir el smbolo inicial de la izquierda
por los smbolos de la derecha, y luego repetir el proceso hasta que
slo haya smbolos terminales. Por ejemplo:A bA bbA bbbA bbbcEsta
gramtica da lugar a unlenguaje formalque 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 unmodelo de reescriturapara
elespaol:1. O SUJ PRED(OracinSujetoPredicado)2. SUJ Det N(Sujeto
DeterminanteNombre)3. PRED V COMP(Predicado VerboComplemento)4. Det
el5. N nio, (hombre, anciano)6. V duerme, (re, come)7. COMP
plcidamente, (intranquilo)Estas reglas pueden utilizarse para
generar la frase "el nio duerme plcidamente", as:1. O(smbolo
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. elN(OMBRE) V(ERBO)
COMP(LEMENTO)(por la regla 4)6. el nioV(ERBO) COMP(LEMENTO)(por la
regla 5)7. el nio duermeCOMP(LEMENTO)(por la regla 6)8. el nio
duerme plcidamente (por la regla 7)Vemos que existen unas
definiciones especiales como FRASE, SUJETO, etc. que no aparecen en
la frase final formada. Son unas entidades abstractas denominadas
"categoras sintcticas" que no son utilizables en una oracin (tienen
un papel similar al de lascategoras gramaticalesde las lenguas
naturales). E igualmente el mismo sistema permite derivar otras
oraciones similares usando formas las formas lxicas entre
parntesis:DetNVCOMP
Elniohombreancianoduermerecomeplcidamenteintranquilo
Las categoras sintcticas definen la estructura del lenguaje
representando porciones ms o menos grandes de las frases. Existe
una jerarqua interna entre las categoras sintcticas.La categora
superior sera la FRASE que representa una oracin vlida en lengua
castellana.Por debajo de ella se encuentran sus componentes.
Ninguna de estas categoras dan lugar a frases vlidas solo la
categora superior.Al finalizar toda la jerarqua llegamos a
laspalabrasque son las unidades mnimas con significado que puede
adoptar una frase.Aplicando las jerarquas y sustituyendo elementos,
llegamos al punto en donde todas las categoras sintcticas se han
convertido en palabras, obteniendo por tanto una oracin vlida; como
por ejemplo:El nio corre. Este proceso se llama produccin o
generacin.Gramticas formales en lingstica terica[editar]Una
gramtica formal es unmodelo matemtico(ms exactamente una estructura
algebraica) compuesto por una serie de categoras sintcticas que se
combinan entre s por medio de unas reglas sintcticas que definen
cmo se crea una categora sintctica por medio de otras o smbolos de
la gramtica. Existen varios tipos de gramticas formales
histricamente importantes: Lasgramticas formales
categoriales(C-gramticas) que usan un anlisis de abajo a arriba y
requieren el uso de etiquetas de categora para cada secuencia
formada oconstituyente sintcticopropiamente dicho. Existe una nica
categora superior que denota cadenas completas y vlidas.
Lasgramticas de estructura sintagmtica(ES-gramticas, en
inglsPS-grammars) basadas enreglas de reescrituray con un anlisis
de arriba abajo. Al igual que las C-gramticas se basan en la nocin
de constituyente sintctico. Lasgramticas asociativas (por la
izquierda)(A-gramticas, en inglsLA-grammars), que usa usa un
anlisis de abajo a arriba, que permiten un anlisis en decomplejidad
lineal, aunque ignoran el concepto de constituyente sintctico.Los
dos primeros tipos tienen puntos de conexin obvia con la nocin
deconstituencia sintcticay el anlisis medianterboles sintcticos.
Sin embargo, los analizadores sintcticos para las oraciones
formadas segn ellas no pueden basarse en las reglas de generacin
(asimetra hablante-oyente), lo cual sugiere que no puedan ser
buenos modelos de la intuicin de los hablantes. Adems los modelos
de lengua natural basados en ellas parecen tener unacomplejidad
polinmicaoexponencial, lo cual no parece avenirse con la velocidad
con que los hablantes procesan las lenguas naturales. Por contra
las A-gramticas en general tienen complejidad lineal, simetra entre
hablantes y oyentes, sin embargo, ignoran los constituyentes
clsicos delanlisis sintctico. Sin embargo, siguen siendo usadas
para losanalizadores sintcticosusados en computacin.Por medio de
estos elementos constituyentes se define un mecanismo de
especificacin consistente en repetir el mecanismo de sustitucin de
una categora por sus constituyentes en funcin de las reglas
comenzando por la categora superior y finalizando cuando la oracin
ya no contiene ninguna categora. De esta forma, la gramtica puede
generar o producir cada una de las cadenas del lenguaje
correspondiente y solo estas cadenas.Definicin de una
C-gramtica[editar]Una gramtica categorial o C-gramtica es una
basada en categoras gramaticales. Las formas lxicas y secuencias
formadas a partir de ellas estn etiquetadas con categoras que
indican el tipo de entidad formada y sus posibilidades
combinatorias (por ejemplo en una lengua nominal una secuencia de
palabras puede constituir un sintagma nominal lo cual especifica
con qu otro tipo de categoras puede combinarse este sintagma para
formar otro sintagma mayor).Las gramticas categoriales se pueden
definir como una estructura formal algebraica. Una gramtica
categorial es un quntuplacon las siguientes propiedades:1. (words)
es el conjunto no vaco de formas bien formadas de la lengua (en una
lengua naturalWpodra interpretarse como secuencias de fonemas que
forman expresiones, irrespectivamente de su categora gramatical).2.
(categories) es el conjunto no vaco de categoras posibles. Para que
este conjunto sea un conjunto de categoras aceptable se exige que
sientonces tambin existan las categoras(frecuentemente denotada
tambin comoY/X) y(frecuentemente denotada tambin comoY\X). Ntese
que de lo anterior se desprende la existencia de las categorasy(sin
ms que intercambiar el papel deXeY).3. El conjunto(lexicon) es un
conjunto, este conjunto es algo diferente dellexicnconvencional ya
que incluye tanto palabras atmicas inanalizables como expresiones
formadas a partir de ellas.4. El conjunto(rules) es un conjunto de
reglas, generalmente formado por las siguientes dos reglas:1. 2.
Las anteriores se aplican a cualesquiera categoras y se interpretan
as: si en un lenguaje formal los elementos a la izquierda de la
regla pertenecen al lexicn, entonces la expresin a la derecha de la
regla tambin es parte del lexicn (es decir, del conjunto de
expresiones posibles en dicho lenguaje). Se comprende que puesto
que la composicin puede ser por la izquierda (regla 1) o por la
derecha (regla 2) se haya requerido que el conjuntoadmita adems de
categoraselas categorasy.5. El conjunto(complete
expresions)Definicin de una ES-gramtica[editar]En la definicin
clsica que dioNoam Chomskyen la dcada de 1950, unagramtica formal
de estructura sintagmtica(ES-gramtica) es unacudruplaG= (N,T,S,P)
donde: Nes un conjunto finito de smbolos no terminales (variables).
Tes un conjunto finito de smbolos terminales
(constantes),disjuntoconN. Ses un smbolo distinguido deN, elsmbolo
inicial. Pes un conjunto finito de reglas de produccin, cada una de
la forma:
donde * es laclausura de Kleene. Esto es, cada regla de
produccin mapea de una cadena de smbolos a otra, donde la primera
cadena contiene al menos un smbolo no terminal. En el caso de que
la segunda cadena sea lacadena vaca, para evitar confusin se la
denota con una notacin especial (usualmente,o).El alfabeto de la
gramtica es entonces el conjuntoDerivaciones[editar]Seauna
gramtica, y sean , , , , , ... palabras de. Entonces: se derivade
en un paso de derivacin, y lo denotamos con si existen dos cadenas,
y una produccin tales que =, y = Notamos conal cierre reflexivo y
transitivo de. Es decir denota a una secuencia de derivaciones en
un nmero finito de pasos desde hasta . es unaforma sentencialde, si
puede obtenerse la siguiente secuencia de derivaciones. En el caso
particular de quese dice que x es unasentencia Se denominalenguaje
formal generado por Gal conjuntoJerarqua de Chomsky[editar]Artculo
principal:Jerarqua de ChomskyCuandoNoam Chomskyformaliz la idea de
lasgramticas generativasen 1956, clasific este tipo de gramticas en
varios tipos de complejidad creciente que forman la llamadajerarqua
de Chomsky. La diferencia entre estos tipos es que cada uno de
ellos tiene reglas ms particulares y restringidas y por tanto
generan lenguajes formales menos generales. Dos tipos importante
son lasgramticas libres de contexto(Tipo 2) y lasgramticas
regulares(Tipo 3). Las lenguas que pueden ser descritas mediante
esos tipos de gramticas sonlenguas libres de contextoylenguas
regulares, respectivamente. Estos dos tipos son mucho menos
generales que las gramticas no restringidas de Tipo 0 (es decir,
que pueden ser procesadas o reconocidas mediantemquinas de Turing).
Estos dos tipos de gramticas se usan ms frecuentemente puesto que
los analizadores sintcticos para estos lenguajes pueden
implementarse de manera eficiente.1Por ejemplo, todas las lenguas
regulares pueden ser reconocidas por unautmata finito. Para
subconjuntos de gramticas libres de contexto, existen algoritmos
para generaranalizadores sintcticos LLyanalizadores sintcticos
LReficientes, que permiten reconocer los correspondientes lenguajes
generados por esas gramticas.Limitacin de las gramticas
formales[editar]Las ES-gramticas como la usada en los primeros
modelos de gramtica generativa requieren ciertas restricciones para
ser computacionalmente tratables. Para entender esa restriccin debe
considerarse la interaccin entre un hablante y un oyente, el
primero genera una oracin o secuencia de acuerdo con las reglas de
la gramtica, el segundo para entender dicha secuencia debe analizar
la secuencia para entenderla, encontrando los elementos formantes,
interpretndolos y reconstruyendo la relacin hay entre ellos
(estructura interna). Para que eso segundo sea posible se requiere
que la estructura interna tenga una estructura suficientemente
simple como poder analizar sintcticamente las secuencias con un
bajo grado de ambigedad. Pues bien computacionalmente se ha
encontrado que laclase de complejidadfrente al anlisis inverso de
ciertas gramticas es excesiva. Para ES-gramticas basadas enreglas
de reescriturase tiene:Restriccionesen las reglasTipo
deES-gramticaTipo delenguajeGrado decomplejidad
tipo 3Gramtica ES regularlenguajes regulareslineal
tipo 2Gramtica ESlibre de contextolenguajes libresde
contextopolinmica
tipo 1Gramtica ESdependiente del contextolenguajes
dependientesdel contextoexponencial
tipo 0Gramtica ESno restringidalenguajes
recursivamenteenumerablesindecidible
Gramticas formales en matemticas y lgica[editar]Dentro
delenfoque formalistay axiomtico de las matemticas se concibi que
ciertas reas de las matemticas podan concebirse como un sistema
lgico-deductivo de frmulas sujetas a restricciones de manipulacin.
La gramtica formal de esos sistemas sera el conjunto de reglas
combinatorias acordes a ciertos principios deductivos.Un lenguaje
formal en lgica o matemticas es una tripletadondedenota el alfabeto
o conjunto de signos usados, el conjunto de reglasexplica qu
combinaciones de signos estn bien definidas y permite definir lo
que es unafrmula bien formada(en ese sentidodefine la morfologa de
las palabras de la lengua formal). El conjunto de frmulas bien
formadas constituyen el vocabulario o lxico, mientras el
pardescribe el conjunto de axiomas y el conjunto de reglas de
deduccin vlidas. Estas dos ltimas permiten establecer secuencias de
frmulas bien formadas (palabras del lenguaje formal) que
constituyen demostraciones vlidas dentro del sistema formal (son de
alguna manera el equivalente a la sintaxis de la lengua
formal).
