Gramática formal

Una gramática categorial o C-gramática es una basada en categorías gramaticales. Las formas léxicas y secuencias formadas a partir de ellas están etiquetadas con categorías 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 categorías puede combinarse este sintagma para formar otro sintagma mayor).

Las gramáticas categoriales se pueden definir como una estructura formal algebraica. Una gramática categorial es un quíntupla ${\displaystyle \scriptstyle (W,C,LX,R,CE)}$ con las siguientes propiedades:

1. ${\displaystyle \scriptstyle W}$ (words) es el conjunto no vacío de formas bien formadas de la lengua (en una lengua natural W podría interpretarse como secuencias de fonemas que forman expresiones, irrespectivamente de su categoría gramatical).
2. ${\displaystyle \scriptstyle C}$ (categories) es el conjunto no vacío de categorías posibles. Para que este conjunto sea un conjunto de categorías aceptable se exige que si ${\displaystyle \scriptstyle X,Y\in C}$ entonces también existan las categorías ${\displaystyle \scriptstyle X{\bar {Y}}\in C}$ (frecuentemente denotada también como Y/X) y ${\displaystyle \scriptstyle {\bar {Y}}X\in C}$ (frecuentemente denotada también como Y\X). Nótese que de lo anterior se desprende la existencia de las categorías ${\displaystyle \scriptstyle X{\bar {Y}}\in C}$ y ${\displaystyle \scriptstyle {\bar {Y}}X\in C}$ (sin más que intercambiar el papel de X e Y).
3. El conjunto ${\displaystyle \scriptstyle LX}$ (lexicon) es un conjunto ${\displaystyle \scriptstyle LX\subset W\times C}$, este conjunto es algo diferente del lexicón convencional ya que incluye tanto palabras atómicas inanalizables como expresiones formadas a partir de ellas.
4. El conjunto ${\displaystyle \scriptstyle R}$ (rules) es un conjunto de reglas, generalmente formado por las siguientes dos reglas:
   1. ${\displaystyle \alpha _{X{\bar {Y}}}\circ \beta _{Y}\rightarrow \alpha \beta _{X}}$
   2. ${\displaystyle \beta _{Y}\circ \alpha _{{\bar {Y}}X}\rightarrow \alpha \beta _{X}}$

   Las anteriores se aplican a cualesquiera categorías y se interpretan así: si en un lenguaje formal los elementos a la izquierda de la regla pertenecen al lexicón ${\displaystyle \scriptstyle LX}$, entonces la expresión a la derecha de la regla también es parte del lexicón (es decir, del conjunto de expresiones posibles en dicho lenguaje). Se comprende que puesto que la composición puede ser por la izquierda (regla 1) o por la derecha (regla 2) se haya requerido que el conjunto ${\displaystyle \scriptstyle C}$ admita además de categorías ${\displaystyle \scriptstyle X}$ e ${\displaystyle \scriptstyle Y}$ las categorías ${\displaystyle \scriptstyle X{\bar {Y}}}$ y ${\displaystyle \scriptstyle {\bar {Y}}X}$.

5. El conjunto ${\displaystyle \scriptstyle CE}$ (complete expresions)

En la definición clásica que dio Noam Chomsky en la década de 1950, una gramática formal de estructura sintagmática (ES-gramática) es una cuádrupla G = (N,T,S,P) donde:

• N es un conjunto finito de símbolos no terminales (variables).
• T es un conjunto finito de símbolos terminales (constantes), disjunto con N.
• S es un símbolo distinguido de N, el símbolo inicial.
• P es un conjunto finito de reglas de producción, cada una de la forma:

${\displaystyle (N\cup T)^{*}N(N\cup T)^{*}\to (N\cup T)^{*}}$

donde * es la clausura de Kleene. Esto es, cada regla de producción mapea de una cadena de símbolos a otra, donde la primera cadena contiene al menos un símbolo no terminal. En el caso de que la segunda cadena sea la cadena vacía, para evitar confusión se la denota con una notación especial (usualmente ${\displaystyle \epsilon \,}$, ${\displaystyle e\,}$ o ${\displaystyle \lambda \,}$).

El alfabeto de la gramática es entonces el conjunto ${\displaystyle \Sigma =N\cup T}$

Sea ${\displaystyle G=(N,T,P,S)}$ una gramática, y sean α, β, δ, φ, ρ, ... palabras de ${\displaystyle \Sigma ^{*}}$. Entonces:

• β se deriva de α en un paso de derivación, y lo denotamos con α ${\displaystyle \Rightarrow }$ β si existen dos cadenas ${\displaystyle \phi _{1},\phi _{2}\in \Sigma ^{*}}$, y una producción δ → ρ tales que α = ${\displaystyle \phi _{1}}$ δ ${\displaystyle \phi _{2}}$, y β = ${\displaystyle \phi _{1}}$ ρ ${\displaystyle \phi _{2}}$
• Notamos con ${\displaystyle \Rightarrow ^{*}}$ al cierre reflexivo y transitivo de ${\displaystyle \Rightarrow }$. Es decir α ${\displaystyle \Rightarrow ^{*}}$ β denota a una secuencia de derivaciones en un número finito de pasos desde α hasta β.
• ${\displaystyle x\in \Sigma ^{*}}$ es una forma sentencial de ${\displaystyle G}$, si puede obtenerse la siguiente secuencia de derivaciones ${\displaystyle S\Rightarrow ^{*}x}$ . En el caso particular de que ${\displaystyle x\in T^{*}}$ se dice que x es una sentencia
• Se denomina lenguaje formal generado por G al conjunto ${\displaystyle L(G)=\{x\in T^{*}|S\Rightarrow ^{*}x\}}$

Cuando Noam Chomsky formalizó la idea de las gramáticas generativas en 1956, clasificó este tipo de gramáticas en varios tipos de complejidad creciente que forman la llamada jerarquía de Chomsky. La diferencia entre estos tipos es que cada uno de ellos tiene reglas más particulares y restringidas y por tanto generan lenguajes formales menos generales. Dos tipos importante son las gramáticas libres de contexto (Tipo 2) y las gramáticas regulares (Tipo 3). Las lenguas que pueden ser descritas mediante esos tipos de gramáticas son lenguas libres de contexto y lenguas regulares, respectivamente. Estos dos tipos son mucho menos generales que las gramáticas no restringidas de Tipo 0 (es decir, que pueden ser procesadas o reconocidas mediante máquinas de Turing). Estos dos tipos de gramáticas se usan más frecuentemente puesto que los analizadores sintácticos para estos lenguajes pueden implementarse de manera eficiente.[1] Por ejemplo, todas las lenguas regulares pueden ser reconocidas por un autómata finito. Para subconjuntos de gramáticas libres de contexto, existen algoritmos para generar analizadores sintácticos LL y analizadores sintácticos LR eficientes, que permiten reconocer los correspondientes lenguajes generados por esas gramáticas.

Las ES-gramáticas como la usada en los primeros modelos de gramática generativa requieren ciertas restricciones para ser computacionalmente tratables. Para entender esa restricción debe considerarse la interacción entre un hablante y un oyente, el primero genera una oración o secuencia de acuerdo con las reglas de la gramática, el segundo para entender dicha secuencia debe analizar la secuencia para entenderla, encontrando los elementos formantes, interpretándolos y reconstruyendo la relación 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 sintácticamente las secuencias con un bajo grado de ambigüedad. Pues bien computacionalmente se ha encontrado que la clase de complejidad frente al análisis inverso de ciertas gramáticas es excesiva. Para ES-gramáticas basadas en reglas de reescritura se tiene:

Hausser, Roland R. (1999). Foundations of Computational Linguistics (en inglés). Springer-Verlag. ISBN 3-540-66015-1.