Gramàtica formal

Esta image mostra la relació entre les cadenes de caràcters, les fòrmules ben formades i els teoremes. En alguns sistemes formals, no obstant, el conjunt de les teoremes coincidix en el de les fòrmules ben formades.

Una gramàtica formal és una estructura llògic-matemàtica en un conjunt de regles de formació que definixen les cadenes de caràcters admissibles en un determinat llenguage formal o llengua natural. Les gramàtiques formals apareixen en varis contexts diferents: la llògica matemàtica, les ciències de la computació i la llingüística teòrica, freqüentment en métodos i interessos divergents.

En un llenguage formal, a les cadenes formades segons les regles de la gramàtica formal li les crida fòrmules ben formades, i el conjunt de totes les fòrmules ben formades constituïx un llenguage formal. Una gramàtica formal no descriu el significat de les fòrmules ben formades, sino solament la seua forma. La teoria dels llenguages formals estudia les gramàtiques formals i els llenguages formals, i és una branca de la matemàtica aplicada. Les seues aplicacions es troben en la ciència computacional teòrica, la llingüística, la semàntica formal, la llògica matemàtica i atres àrees.

Introducció

Una gramàtica formal és un conjunt de regles per a reescriure cadenes de caràcters, junt en un símbol inicial des del qual deu escomençar la reescritura. Per lo tant, una gramàtica formal generalment es pensa com una generadora de llenguages. No obstant, a voltes també pot ser usada com la base per a un "reconocedor": una funció que determina si una cadena qualsevol pertany a un llenguage o és gramaticalmente incorrecta.

Hi ha distints tipos de gramàtiques formals que generen llenguages formals (vore la jerarquia de Chomsky). Imaginem una gramàtica en estes dos regles:

1. A → bA
2. A → c

L'element en mayúscules és el símbol inicial. Els elements en minúscules són els símbols terminals. Per a generar cadenes de caràcters, l'idea és substituir el símbol inicial de l'esquerra pels símbols de la dreta, i després repetir el procés fins que només hi haja símbols terminals. Per eixemple:

A → bA → bbA → bbbA → bbbc

Esta gramàtica dona lloc a un llenguage formal que consistix en el conjunt de totes les cadenes de caràcters que poden ser generades per mig elles. Per eixemple: bbbc, bbbbbbbbc, c, bc, etc.

Per a comprendre millor l'idea, podem considerar un modele de reescritura per al espanyol:

1. O → SUJ PRED (Oració → Subjecte Predicat)
2. SUJ → Det N (Subjecte → Determinant Nom)
3. PRED → V COMP (Predicat → Verp Complement)
4. DET → el #

N → chiquet, (home, vell)

1. V → dorm, (riu, menja)
2. COMP → plácidamente, (intranquilo)

Estes regles poden utilisar-se per a generar la frase "el chiquet dorm plácidamente", aixina:

1. O(RACIÓN) (símbol inicial)
2. SUJ(ETO) PRED(ICADO) (per la regla 1)
3. DET(ERMINANTE) N(OMBRE) PRED(ICADO) (per la regla 2)
4. DET(ERMINANTE) N(OMBRE) V(ERBO) COMP(LEMENTO) (per la regla 3)
5. el N(OMBRE) V(ERBO) COMP(LEMENTO) (per la regla 4)
6. el chiquet V(ERBO) COMP(LEMENTO) (per la regla 5)
7. el chiquet dorm COMP(LEMENTO) (per la regla 6)

1. el chiquet dorm plácidamente (per la regla 7)

Veem que existixen unes definicions especials com ORACIÓN, SUJETO, etc. que no apareixen en la frase final formada. Són unes entitats abstractes denominades "categories sintàctiques" que no són utilisables en una oració (tenen un paper similar al de les categories gramaticals de les llengües naturals). I igualment el mateix sistema permet derivar atres oracions similars usant formes les formes lèxiques entre paréntesis:

Det	N	V	COMP
El	chiquet home vell	dorm riu menja	plácidamente intranquilo

Les categories sintàctiques definixen l'estructura del llenguage representant porcions més o menys grans de les frases. Existix una jerarquia interna entre les categories sintàctiques.

La categoria superior seria la FRASE que representa una oració vàlida en llengua castellana.

Per baix d'ella es troben els seus components. Cap d'estes categories donen lloc a frases vàlides solament la categoria superior.

En finalisar tota la jerarquia apleguem a les paraules que són les unitats mínimes en significat que pot adoptar una frase.

Aplicant les jerarquia i substituint elements, apleguem al punt en a on totes les categories sintàctiques s'han convertit en paraules, obtenint per tant una oració vàlida; com per eixemple: El chiquet corre. Este procés es diu producció o generació.

Gramàtiques formals en llingüística teòrica

Una gramàtica formal és un model matemàtic (més exactament una estructura algebraica) compost per una série de categories sintàctiques que es combinen entre sí per mig d'unes regles sintàctiques que definixen cóm es crea una categoria sintàctica per mig d'unes atres o símbols de la gramàtica. Existixen varis tipos de gramàtiques formals històricament importants:

• Les gramàtiques formals categorials (C-gramàtiques) que usen un anàlisis d'avall dalt i requerixen l'us d'etiquetes de categoria per a cada seqüència formada o constituent sintàctic pròpiament dit. Existix una única categoria superior que denota cadenes completes i vàlides.
• Les gramàtiques d'estructura sintagmática (ES-gramàtiques, en anglés PS-grammars) basades en regles de reescritura i en un anàlisis de dalt avall. De la mateixa manera que les C-gramàtiques es basen en la noció de constituent sintàctic.
• Les gramàtiques associatives (per l'esquerra) (A-gramàtiques, en anglés LA-grammars), que usa usa un anàlisis d'avall dalt, que permeten un anàlisis de complexitat llineal, encara que ignoren el concepte de constituent sintàctic.

Els dos primers tipos tenen punts de conexió òbvia en la noció de constituencia sintàctica i l'anàlisis per mig d'arbres sintàctics. No obstant, els analisadors sintàctics per a les oracions formades segons elles no poden basar-se en les regles de generació (asimetria parlant-escoltant), lo que sugerix que no puguen ser bons models de l'intuïció dels parlants. Ademés els models de llengua natural basats en elles semblen tindre una complexitat polinòmica o exponencial, lo que no sembla avenirse en la velocitat en que els parlants processen les llengües naturals. En canvi les A-gramàtiques en general tenen complexitat llineal, simetria entre parlants i escoltants, no obstant, ignoren els constituents clàssics del anàlisis sintàctic. No obstant, seguixen sent usades per als analisadors sintàctics usats en computació.

Per mig d'estos elements constituents es definix un mecanisme d'especificació consistent en repetir el mecanisme de substitució d'una categoria pels seus constituents en funció de les regles començant per la categoria superior i finalisant quan l'oració ya no conté cap categoria. D'esta forma, la gramàtica pot generar o produir cada una de les cadenes del llenguage corresponent i solament estes cadenes.

Definició d'una C-gramàtica

Una gramàtica categorial o C-gramàtica és una basada en categories gramaticals. Les formes lèxiques i seqüències formades a partir d'elles estan etiquetades en categories que indiquen el tipo d'entitat formada i les seues possibilitats combinatòries (per eixemple en una llengua nominal una seqüència de paraules pot constituir un sintagma nominal lo que especifica en quin un atre tipo de categories pot combinar-se este sintagma per a formar un atre sintagma major).

Les gramàtiques categorials es poden definir com una estructura formal algebraica. Una gramàtica categorial és un quíntupla $(W,C,LX,R,CE)$ en les següents propietats:

1. $W$ (words) és el conjunt no buit de formes ben formades de la llengua (en una llengua natural W podria interpretar-se com a seqüències de fonema que formen expressions, irrespectivamente de la seua categoria gramatical).
2. $C$ (categories) és el conjunt no buit de categories possibles. Per a que este conjunt siga un conjunt de categories acceptable s'exigix que si $X,Y\in C$ llavors també existixquen les categories $X\overline{Y}\in C$ (freqüentment denotada també com I/X) i $\overline{Y}X\in C$ (freqüentment denotada també com I'X). Note's que de lo anterior es desprén l'existència de les categories $X\overline{Y}\in C$ i $\overline{Y}X\in C$ (sense més que intercanviar el paper de X i I).
3. El conjunt $LX$ (lexicon) és un conjunt $LX\subset W\times C$, este conjunt és alguna cosa diferent del lexicón convencional ya que inclou tant paraules atòmiques inanalizables com a expressions formades a partir d'elles.
4. El conjunt $R$ (rules) és un conjunt de regles, generalment format per les següents dos regles:
   1. ${\alpha }_{X\overline{Y}}\circ {\beta }_Y\to \alpha {\beta }_X$
   2. ${\beta }_Y\circ {\alpha }_{\overline{Y}X}\to \alpha {\beta }_X$

   Les anteriors s'apliquen a qualssevol categories i s'interpreten aixina: si en un llenguage formal els elements a l'esquerra de la regla pertanyen al lexicón $LX$, llavors l'expressió a la dreta de la regla també és part del lexicón (és dir, del conjunt d'expressions possibles en dit llenguage). Es comprén que posat que la composició pot ser per l'esquerra (regla 1) o per la dreta (regla 2) s'haja requerit que el conjunt $C$ admeta ademés de categories $X$ i $Y$ les categories $X\overline{Y}$ i $\overline{Y}X$.

5. El conjunt $CE$ (complete expresions)

Definició d'una ES-gramàtica

En la definició clàssica que va donar Noam Chomsky en la década de 1950, una gramàtica formal d'estructura sintagmática (ES-gramàtica) és una cuádrupla G = (N,T,S,P) a on:

• N és un conjunt finit de símbols no terminals (variables).
• T és un conjunt finit de símbols terminals (constants), disjunto en N.
• S és un símbol distinguit de N, el símbol inicial.
• P és un conjunt finit de regles de producció, cada una de la forma:

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

a on * és la clausura de Kleene. Açò és, cada regla de producció mapea d'una cadena de símbols a una atra, a on la primera cadena conté a lo manco un símbol no terminal. En el cas de que la segona cadena siga la cadena buida, per a evitar confusió li la denota en una notació especial (usualment $ϵ$, $e$ o $\lambda$).

L'alfabet de la gramàtica és llavors el conjunt $\Sigma =N\cup T$

Derivació

Siga $G=(N,T,P,S)$ una gramàtica, i siguen α, β, δ, φ, ρ, ... paraules de ${\Sigma }^{*}$. Llavors:

• β es deriva de α en un pas de derivació, i ho denotem en α $\Rightarrow$ β si existixen dos cadenes ${\varphi }_1,{\varphi }_2\in {\Sigma }^{*}$, i una producció δ → ρ tals que α = ${\varphi }_1$ δ ${\varphi }_2$, i β = ${\varphi }_1$ ρ ${\varphi }_2$
• Notem en ${\Rightarrow }^{*}$ al tancament reflexiu i transitivo de $\Rightarrow$. És dir α ${\Rightarrow }^{*}$ β denota a una seqüència de derivació en un número finit de passos des de α fins a β.

• $x\in {\Sigma }^{*}$ és una forma sentencial de $G$, si pot obtindre's la següent seqüència de derivació $S{\Rightarrow }^{*}x$ . En el cas particular de que $x\in T^{*}$ es diu que x és una sentència
• Es denomina llenguage formal generat per G al conjunt $L(G)=\{x\in T^{*}|S{\Rightarrow }^{*}x\}$

Jerarquia de Chomsky

Artícul principal → Jerarquia de Chomsky.

Quan Noam Chomsky va formalisar l'idea de les gramàtiques generativas en 1956, va classificar este tipo de gramàtiques en varis tipos de complexitat creixent que formen la cridada jerarquia de Chomsky. La diferència entre estos tipos és que cada u d'ells té regles més particulars i restringides i per tant generen llenguages formals menys generals. Dos tipos important són les gramàtiques lliures de context (Tipo 2) i les gramàtiques regulars (Tipo 3). Les llengües que poden ser descrites per mig d'eixos tipos de gramàtiques són llengües lliures de context i llengües regulars, respectivament. Estos dos tipos són molt manco generals que les gramàtiques no restringides de Tipo 0 (és dir, que poden ser processades o reconegudes per mig de màquines de Turing). Estos dos tipos de gramàtiques s'usen més freqüentment posat que els analisadors sintàctics per a estos llenguages poden implementar-se de manera eficient. Per eixemple, totes les llengües regulars poden ser reconegudes per un autómata finit. Per a subconjunts de gramàtiques lliures de context, existixen algoritmes per a generar analisadors sintàctics LL i analisadors sintàctics LR eficients, que permeten reconéixer els corresponents llenguages generats per eixes gramàtiques.

Llimitació de les gramàtiques formals

Les ES-gramàtiques com l'usada en els primers models de gramàtica generativa requerixen certes restriccions per a ser computacionalment tractables. Per a entendre eixa restricció deu considerar-se l'interacció entre un parlant i un oyent, el primer genera una oració o seqüència d'acort en les regles de la gramàtica, el segon per a entendre dita seqüència deu analisar la seqüència per a entendre-la, trobant els elements formantes, interpretant-los i reconstruint la relació hi ha entre ells (estructura interna). Per a que això segon siga possible es requerix que l'estructura interna tinga una estructura suficientment simple com poder analisar sintácticamente les seqüències en un baix grau d'ambigüitat. Puix ben computacionalment s'ha trobat que la classe de complexitat front a l'anàlisis invers de certes gramàtiques és excessiva. Per a ES-gramàtiques basades en regles de reescritura es té:

Restriccions en les regles	Tipo de ES-gramàtica	Tipo de llenguage	Grau de complexitat
tipo 3	Gramàtica ES regular	llenguages regulars	llineal
tipo 2	Gramàtica ES lliure de context	llenguages lliures de context	polinòmica
tipo 1	Gramàtica ES dependent del context	llenguages depenents del context	exponencial
tipo 0	Gramàtica ES no restringida	llenguages recursivamente enumerables	indecidible

Vore també

• Jerarquia de Chomsky
• Analisador sintàctic

Referències

Bibliografia

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