Grammatiche

Note

A differenza dei modelli di linguaggio/calcolo visti finora, che definiscono un linguaggio tramite l'elaborazione della stringa che gli appartiene, la grammatica o sintassi è un modello generativo. In generale, è un insieme di regole per generare frasi di un linguaggio.

Formalmente, una grammatica è una quadrupla , composta rispettivamente da:

Un alfabeto o vocabolario terminale
Un alfabeto o vocabolario non terminale
Un alfabeto o vocabolario
Un assioma o simbolo iniziale
Insieme delle produzioni sintattiche o regole di riscrittura

Le regola di una grammatica descrivono un "oggetto principale" come un insieme ordinato di "componenti". La descrizione è fornita fino ad arrivare al livello di dettaglio desiderato. Spesso si tende a chiamare lessico la descrizione grammaticale delle singole parole, sintassi quella della loro composizione.

Per semplicità di notazione, indicheremo gli elementi come .

Regole di derivazione

Note

Definiamo la relazione di derivazione immediata per una grammatica come se e solo se e . Dove non ambiguo, è possibile omettere il pedice che indica la grammatica. Inoltre definiamo come la chiusura riflessiva e transitiva di . Il linguaggio generato dalla grammatica è l'insieme di tutte e sole le stringhe di soli caratteri di tali che .

Esempio linguaggio generatore di

Definiamo la grammatica con .
Si ha che una possibile derivazione è: Un altra possibile derivazione è: Quindi il linguaggio generato è .

Esempio linguaggio ben parentetizzato

Si ha . Si discerne che genera un linguaggio di coppie di e ben parentetizzate.

Espressività delle grammatiche

Note

È possibile categorizzare le grammatiche in base alla loro espressività. Per farlo si usa la gerarchia di Chomsky:

Tipo	Nome	Limitazione
0	Non limitate	nessuna
1	Monotone (non-decreasing)
1	Dipendenti dal contesto
2	Libere dal contesto
3	Regolari	Di forma oppure con e

Conversione FSA - Grammatiche regolari

Per passare da un FSA ad una grammatica poniamo , e . Si ha che per ogni aggiungiamo all'insieme , e se per una data , aggiungiamo anche all'insieme . È dimostrabile per induzione che se e solo se .

Viceversa, per passare da una grammatica ad un FSA ND, poniamo , e . Abbiamo che se allora , e se allora .

Grammatiche libere dal contesto e AP-ND

I linguaggi generati dalle grammatiche libere dal contesto coincidono con i linguaggi riconosciuti dagli AP non deterministici. Le dimensioni fisiche della funzione di rete dipendono dalle dimensioni fisiche dei fasori.

Grammatiche non limitate e MT

Le grammatiche non limitate corrispondono alla MT. Emuliamo una MT a nastro singolo con una grammatica non ristretta. Considerato che può "manipolare" solo elementi di , faccio in modo che generi stringhe della forma , con e che è costituita da coppia non terminali degli elementi di .

Si ha che le grammatiche di tipo corrispondono a un sottoinsieme delle MT di cui è certo che terminino sempre.