Gramàtica formal

Aquesta imatge mostra la relació entre les cadenes de caràcters, les fórmules ben formades i els teoremes. En alguns sistemes formals, però, el conjunt dels teoremes coincideix amb el de les fórmules ben formades.

Una gramàtica formal és un objecte o model matemàtic que permet especificar un llenguatge o llengua, és a dir, és el conjunt de regles capaços de generar totes les possibilitats combinatòries de l'idioma, ja sigui aquest un llenguatge formal o un llenguatge natural.

Introducció

L'expressió «gramàtica formal» té dos sentits:

gramàtica d'un llenguatge formal .
descripció formal de part de la gramàtica d'un llenguatge natural.

Quan ens referim a llenguatge natural aquestes regles combinatòries reben el nom de sintaxi, i són inconscients.

Hi ha diferents tipus de gramàtiques formals que generen llenguatges formals (vegeu la Jerarquia de Chomsky). Imaginem una gramàtica amb aquestes dues regles:

A? bac
A? de

La idea és substituir el símbol inicial de l'esquerra per altres símbols aplicant les regles. El llenguatge al qual representa aquesta gramàtica és el conjunt de cadenes de símbols que poden ser generats d'aquesta manera: en aquest cas, per exemple:

A? bac? bbAcc? bbbAccc? bbbdeccc.

L'element en majúscules és el símbol inicial. Els elements en minúscules són símbols terminals. Les cadenes de la llengua són aquelles que només contenen elements terminals, com per exemple:

bbbdeccc, de, BDECA, ... Aquestes serien tres possibles realitzacions del llenguatge la gramàtica hem definit amb dues regles.

Per comprendre millor el concepte posarem algunes regles de la gramàtica castellana:

Una FRASE es pot compondre de SUBJECTE+PREDICAT

O=SN+SV

Un subjecte es pot compondre d'un ARTICLE+NOM o SUBSTANTIU (nucli)+Complements

SN=Det+N+C

Un PREDICAT es pot compondre d'un VERB conjugat

SV=Aux+GV

Un article pot ser la paraula "el"
Un NOM o substantiu pot ser "nen"
Etc. [Vegeu Regles de reescriptura]

Veiem que hi ha unes definicions especials com FRASE, subjecte, etc. que no apareixen en la frase final formada. Són unes entitats abstractes anomenades Categories sintàctiques que no són utilitzables en una frase.

Les categories sintàctiques defineixen l'estructura del llenguatge representant porcions més o menys grans de les frases. Hi ha una jerarquia interna entre les categories sintàctiques.

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

Per sota d'ella es troben els seus components. Cap d'aquestes categories donen lloc a frases vàlides només la categoria superior.

En finalitzar tota la jerarquia arribem a les paraules que són les unitats mínimes amb significat que pot adoptar una frase.

Aplicant les jerarquies i substituint elements, arribem al punt on totes les categories sintàctiques s'han convertit en paraules, obtenint per tant una oració vàlida, com per exemple: El nen corre . Aquest procés s'anomena producció o generació.

Elements constituents

Una gramàtica formal és un model matemàtic compost per una sèrie de categories sintàctiques que es combinen entre si per mitjà d'unes regles sintàctiques que defineixen com es crea una categoria sintàctica per mitjà d'altres o símbols de la gramàtica.
Hi ha una única categoria superior que denota cadenes completes i vàlides.

Mecanismes d'especificació

Per mitjà d'aquests elements constituents es defineix un mecanisme d'especificació consistent a repetir el mecanisme de substitució d'una categoria pels seus constituents en funció de les regles començant per la categoria superior i finalitzant quan l'oració ja no conté cap categoria.

D'aquesta manera, la gramàtica pot generar o produir cada una de les cadenes del llenguatge corresponent i només aquestes cadenes.

Definició formal

En la definició clàssica que va donar Noam Chomsky En la dècada de 1950, una gramàtica formal és una quàdruple G = ( N , T , S , P ) on:

N és un conjunt finit de símbols no terminals (variables).
T és un conjunt finit de símbols terminals (constants), disjunt amb N .
S és un símbol distingit d'N, el símbol inicial .
P és un conjunt finit de regles de producció, cadascuna de la forma:

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

on * és la clausura de Kleene. És a dir, cada regla de producció mapeja d'una cadena de símbols a una altra, on la primera cadena conté com a mínim un símbol no terminal. En el cas que la segona cadena sigui la cadena buida, per evitar confusió se la denota amb una notació especial (normalment $\epsilon \,$ , $i\,$ o $\lambda \,$ ).

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

Derivacions

Sigui $G=(N,T,P,S)$ una gramàtica, i siguin a, ß, d, f,?, ... paraules de $\Sigma ^{*}$ . Llavors

ß es deriva d'a en un pas de derivació, i ho denotem amb a $\Rightarrow$ ß si hi ha dues cadenes $\phi _{1},\phi _{2}\in \Sigma ^{*}$ , i una producció d?? tals que a = $\phi _{1}$ d $\phi _{2}$ , i ß = $\phi _{1}$ ? $\phi _{2}$

Notem amb $\Rightarrow ^{*}$ al tancament reflexiu i transitiu de $\Rightarrow$ . És a dir a $\Rightarrow ^{*}$ ß denota a una seqüència de derivacions en un nombre finit de passos des de a fins a ß.

$X\in \Sigma ^{*}$ és una forma sentencial de $G$ , si pot obtenir la seqüència de derivacions $S\Rightarrow ^{*}x$ . En el cas particular que $x\in T^{*}$ es diu que x és una sentència

Es denomina llenguatge formal generat per G al conjunt $L(G)=\{x\in T^{*}|S\Rightarrow ^{*}x\}$