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 $A\to a,\space A\to aA$ oppure $A\to a,\space A\to Aa$ con $a\in V_{t}$ e $A\in V_{n}$			 |

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.