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 $G=⟨V_t,V_n,P,S⟩$, composta rispettivamente da:

• Un alfabeto o vocabolario terminale $V_t$
• Un alfabeto o vocabolario non terminale $V_n$
• Un alfabeto o vocabolario $V=V_n\cup V_t$
• Un assioma o simbolo iniziale $S\in V_n$
• Insieme delle produzioni sintattiche o regole di riscrittura $P\subseteq V_n^{+}\times V^{\ast }$

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 $p\in Pp=⟨\alpha ,\beta ⟩$ come $p=\alpha \to \beta$.

Regole di derivazione

Note

Definiamo la relazione di derivazione immediata $\underset{G}{\Rightarrow }$ per una grammatica $G=⟨V_t,V_n,P,S⟩$ come $\alpha \underset{G}{\Rightarrow }\beta$ se e solo se $\alpha \in V^{+},\beta \in V^{\ast }$ e $\alpha ={\alpha }_1{\alpha }_2{\alpha }_3\beta =a_1{\beta }_2{\alpha }_3{\alpha }_2\to {\beta }_2\in P$. Dove non ambiguo, è possibile omettere il pedice $G$ che indica la grammatica. Inoltre definiamo $\stackrel{\ast }{\Rightarrow }$ come la chiusura riflessiva e transitiva di $\Rightarrow$. Il linguaggio $L(G)$ generato dalla grammatica $G$ è l’insieme di tutte e sole le stringhe $x$ di soli caratteri di $V_t$ tali che $S\stackrel{\ast }{\Rightarrow }x$.

Esempio linguaggio generatore di $L(G)=\{a^{\ast }{b}^{\ast }{c}^{\ast }\}$

Definiamo la grammatica $G=⟨\{a,b,c\},\{S,A,B,C\},S,P⟩$ con $P=\{S\to A,A\to aA,A\to B,B\to bB,B\to C,C\to cC,C\to \epsilon \}$. Si ha che una possibile derivazione è:

$$S\Rightarrow A\Rightarrow aA\Rightarrow aaA\Rightarrow aaB\Rightarrow aaC\Rightarrow aacC\Rightarrow aaccC\Rightarrow aacccC\Rightarrow aacccC\Rightarrow aaccc$$

Un altra possibile derivazione è:

$$S\Rightarrow A\Rightarrow B\Rightarrow bB\Rightarrow bC\Rightarrow b$$

Quindi il linguaggio generato è $L(G)=\{a^{\ast }{b}^{\ast }{c}^{\ast }\}$.

Esempio linguaggio ben parentetizzato

Si ha $G=⟨\{a,b\},\{S\},S,\{S\to aSbS,S\to \epsilon \}⟩$. Si discerne che genera un linguaggio di coppie di $a$ e $b$ 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)

$$\alpha \to \beta \Vert \alpha \Vert \le \Vert \beta \Vert$$

  																		|

| 1 | Dipendenti dal contesto |

$$\alpha \to \beta \alpha =\gamma As\beta =\gamma \chi \delta \chi \ne \epsilon \text{ o }S\to \epsilon$$

   |

| 2 | Libere dal contesto |

$$\alpha \to \beta \Vert \alpha \Vert =1$$

  																						|
  | 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 $V_n=Q$, $V_t=I$ e $S=⟨q_0⟩$. Si ha che per ogni $\delta (q,i)=q^{\prime }$ aggiungiamo $⟨q⟩\to i⟨q^{\prime }⟩$ all’insieme $P$, e se $q^{\prime }\in F$ per una data $\delta (q,i)=q^{\prime }$, aggiungiamo anche $⟨q⟩\to i$ all’insieme $P$. È dimostrabile per induzione che ${\delta }^{\ast }(q_0,x)=q^{\prime }$ se e solo se $⟨q_0⟩⟹x⟨q^{\prime }⟩$.

Viceversa, per passare da una grammatica ad un FSA ND, poniamo $Q=V_n\cup \{q_f\}$, $I=V_t$ e $F=\{q_f\}$. Abbiamo che se $A\to bC\in P$ allora $\delta (A,b)=C$, e se $A\to b\in P$ allora $\delta (A,b)=q_f$.

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 $\mathcal{M}$ a nastro singolo con una grammatica $G$ non ristretta. Considerato che $G$ può “manipolare” solo elementi di $V_n$, faccio in modo che generi stringhe della forma $x\diamond X$, con $\diamond \in V_n,x\in V_t^{\ast }$ e $X$ che è costituita da coppia non terminali degli elementi di $X$.

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