Gramática formal

Unha gramática formal é unha estrutura matemática cun conxunto de regras de formación que definen as cadeas de caracteres admisibles nunha determinada linguaxe formal ou linguaxe natural. As gramáticas formais aparecen en varios contextos diferentes: a lóxica matemática, as ciencias da computación e a lingüística teórica, a miúdo con métodos e intereses diverxentes.

Nunha linguaxe formal, s cadeas formadas segundo as regras da gramática formal chámanse fórmulas ben formadas, e o conxunto de tódalas fórmulas ben formadas constitúe unha linguaxe formal. Unha gramática formal non describe o significado das fórmulas ben formadas, senón soamente a súa forma. A teoría das linguaxes formais estuda as gramáticas formais e as linguaxes formais, e é unha póla da matemática aplicada. As súas aplicacións atópanse na ciencia computacional teórica, a lingüística, a semántica formal, a lóxica matemática e outras áreas.

Unha gramática formal é un conxunto de regras para reescribir cadeas de caracteres, xunto cun símbolo inicial dende o cal debe comezar a reescritura. Polo tanto, unha gramática formal xeralmente pénsase como unha xeradora de linguaxes. Porén, ás veces tamén pode ser empregada como a base para un "recoñecedor": unha función que determina se unha cadea calquera pertence a unha linguaxe ou é gramaticalmente incorrecta.

Hai distintos tipos de gramáticas formais que xeran linguaxes formales (como a xerarquía de Chomsky). Imaxinemos unha gramática con estas dúas regras:

1. A → bA
2. A → c

O elemento en maiúsculas é o símbolo inicial. Os elementos en minúsculas son os símbolos terminais. Para xerar cadeas de caracteres, a idea é substituír o símbolo inicial da esquerda polos símbolos da dereita, e logo repetir o proceso até que só haxa símbolos terminais. Por exemplo:

A → bA → bbA → bbbA → bbbc

Esta gramática dá lugar a unha linguaxe formal que consiste no conxunto de tódalas cadeas de caracteres que poden ser xeradas por medio delas. Por exemplo: bbbc, bbbbbbbbc, c, bc etc.

Para comprender mellor a idea, podemos considerar un modelo de reescritura para o galego:

1. O → SUX PRED (Oración → Suxeito Predicado)
2. SUX → Det N (Suxeito → Determinante Nome)
3. PRED → V COMP (Predicado → Verbo Complemento)
4. Det → o
5. N → neno, (home, ancián)
6. V → dorme, (ri, come)
7. COMP → calmo, (inquedo)

Estas regras poden utilizarse para xerar a frase "o neno dorme calmo", así:

1. O (símbolo inicial)
2. SUX(EITO) PRED(ICADO) (pola regra 1)
3. Det(erminante) N(OME) PRED(ICADO) (pola regra 2)
4. Det(erminante) N(OME) V(ERBO) COMP(LEMENTO) (pola regra 3)
5. o N(OMBRE) V(ERBO) COMP(LEMENTO) (pola regra 4)
6. o neno V(ERBO) COMP(LEMENTO) (pola regra 5)
7. o neno dorme COMP(LEMENTO) (pola regra 6)
8. o neno dorme calmo (pola regra 7)

Vemos que existen unhas definicións especiais como FRASE, SUXEITO etc. que non aparecen na frase final formada. Son unhas entidades abstractas denominadas "categorías sintácticas" que non son utilizables nunha oración (teñen un papel semellante ó das categorías gramaticais das linguas naturais). E igualmente o mesmo sistema permite derivar outras oracións semellantes empregando as formas léxicas entre paréntese:

Det	N	V	COMP
O	neno home ancián	dorme ri come	calmo inquedo

As categorías sintácticas definen a estrutura da linguaxe representando anacos máis ou menos grandes das frases. Existe unha xerarquía interna entre as categorías sintácticas. A categoría superior sería a FRASE que representa unha oración válida en lingua galega. Por debaixo dela atópanse os seus compoñentes. Ningunha destas categorías dan lugar a frases válidas, só a categoría superior. Ó rematar toda a xerarquía chegamos ás palabras que son as unidades mínimas con significado que pode adoptar unha frase.

Aplicando as xerarquías e substituíndo elementos, chegamos ó punto onde todas as categorías sintácticas se converten en palabras, obtendo polo tanto unha oración válida; como por exemplo: O neno ri. Este proceso chámase produción ou xeración.

Sexa ${\displaystyle G=(N,T,P,S)}$ unha gramática, e sexan α, β, δ, φ, ρ, ... palabras de ${\displaystyle \Sigma ^{*}}$ . Entón

• β derivase de α nun paso de derivación, e denotámolo con α ${\displaystyle \Rightarrow }$ β se existen dúas cadas ${\displaystyle \phi _{1},\phi _{2}\in \Sigma ^{*}}$, e unha produción δ → ρ tales que α = ${\displaystyle \phi _{1}}$ δ ${\displaystyle \phi _{2}}$, e β = ${\displaystyle \phi _{1}}$ ρ ${\displaystyle \phi _{2}}$
• Notamos con ${\displaystyle \Rightarrow ^{*}}$ o peche reflexivo e transitivo de ${\displaystyle \Rightarrow }$. É dicir α ${\displaystyle \Rightarrow ^{*}}$ β denota unha secuencia de derivacións nun número arbitrario de pasos dende α ata β.
• ${\displaystyle x\in \Sigma ^{*}}$ é unha forma sentencial de ${\displaystyle G}$, pódese obter a seguinte secuencia de derivacións ${\displaystyle S\Rightarrow ^{*}x}$ . No caso particular de que ${\displaystyle x\in T^{*}}$ dise que x é unha sentenza
• Denomínase linguaxe formal xerado por G ó conxunto ${\displaystyle L(G)=\{x\in T^{*}|S\Rightarrow ^{*}x\}}$

Cando Noam Chomsky formalizou a idea das gramáticas xenerativas en 1956, clasificou este tipo de gramáticas en varios tipos de complexidade crecente que forman a chamada xerarquía de Chomsky. A diferenza entre estes tipos é que cada un deles ten regras máis particulares e restrinxidas e polo tanto xeran linguaxes formais menos xerais. Dous tipos importante son as gramáticas libres de contexto (Tipo 2) e as gramáticas regulares (Tipo 3). As linguas que poden ser descritas mediante eses tipos de gramáticas son linguas libres de contexto e linguas regulares, respectivamente. Estes dous tipos son moito menos xerais que as gramáticas non restrinxidas de Tipo 0 (é dicir, que poden ser procesadas ou recoñecidas mediante máquinas de Turing). Estes dous tipos de gramáticas úsanse máis a miúdo posto que os analizadores sintácticos para estas linguaxes poden poñerse en funcionamento de xeito eficiente.^[1] Por exemplo, todas as linguas regulares poden ser recoñecidas por un autómata finito. Para subconxuntos de gramáticas libres de contexto, existen algoritmos para xerar analizadores sintácticos LL e analizadores sintácticos LR eficientes, que permiten recoñecer as correspondentes linguaxes xeradas por esas gramáticas.

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