Grammatiche: equivalenze, forme normali e trasformazioni

Introduciamo in questa lezione altri concetti delle grammatiche che ci aiutano a definire i linguaggi formali.

Equivalenza di due grammatiche

Dividiamo l'equivalenza di due grammatiche in due tipi: equivalenza forte (detta anche equivalenza strutturale) e equivalenza debole.

Due grammatiche $G$ e $G^{\prime }$ sono debolmente equivalenti se generano lo stesso linguaggio $L(G)=L(G^{\prime })$.

Si noti che con questa definizione le due grammatiche possono generare una stessa stringa attraverso due differenti alberi di derivazione. L'albero di derivazione utilizzato si dice assegnato a una stringa.

Due grammatiche $G$ e $G^{\prime }$ sono fortemente o strutturalmente equivalenti se sono debolmente equivalenti e gli alberi di derivazione condensati sono uguali.

Quindi alla luce delle definizioni, se una grammatica è fortemente equivalente è anche debolmente equivalente, ma non viceversa. Stabilire se due grammatiche sono debolmente equivalenti è un problema indecidibile, viceversa stabilire se due grammatiche sono fortemente equivalenti è un problema decidibile.

Esempio

Vedi la pagina degli esercizi.

Grammatiche in forma normale

Le forme normali sono regole che permettono di modificare una grammatica senza però variarne il linguaggio generato. Queste forme sono molto usate in teoria per semplificare dimostrazioni di teoremi. Tuttavia nella pratica non sono molto usate, perché introducono una forma prolissa e poco leggibile. L'importanza di queste forme sarà più chiara nelle prossime lezioni.

Nella prossima sezione vedremo come avvengono le trasformazioni, qui ci limitiamo a elencare le forme normali:

• grammatica senza termini annullabili: una grammatica che non presenta in nessuna regola (ad eccezione dell'assioma) un termine annullabile, ovvero non presenta $ϵ$ nella sua definizione.
• grammatica non ricorsiva a sinistra: come dice il nome, è una grammatica che non presenta regole ricorsive a sinistra; le regole ricorsive si presenteranno tutte nella forma a destra $A\to \varphi A|...$
• grammatica in forma di Chmosky o binaria: le regole della grammatica si presentano solo in due forme:
  • omogenea binaria: $A\to BC,B,C\in V$
  • terminale con singleton a destra: $A\to a\in \mathrm{\Sigma }$
• grammatica in forma real-time: ogni regola inizia con un terminale, cioè ogni regola è nella forma $A\to a\alpha$ con $a\in \mathrm{\Sigma },\alpha \in \{\mathrm{\Sigma }\cup V{\}}^{*}$
• grammatica in forma di Greibach: ogni regola inizia con un terminale seguito da uno o più non terminali, cioè ogni regola è nella forma $A\to a\alpha$ con $a\in \mathrm{\Sigma },\alpha \in V^{*}$

Attraverso la forma di Chmosky, nell'albero di sintassi un nodo può avere come figli (di primo grado) solo due non terminali o un terminale.

Trasformazioni di grammatiche

Definiamo inizialmente alcune operazioni che poi utilizzeremo per portare le grammatiche in forma normale.

Espansione di un non terminale

Come dice il titolo, un'operazione molto semplice consiste nel sostituire ovvero espandere un nonterminale:

$A\to \alpha B\gamma$

$B\to {\beta }_1|{\beta }_2|{\beta }_3|...$

Diventa:

$A\to \alpha {\beta }_1\gamma |\alpha {\beta }_2\gamma |\alpha {\beta }_3\gamma |...$

$B\to {\beta }_1|{\beta }_2|{\beta }_3|...$

Eliminazione dell'assioma nella parte destra

Senza perdere di generalità è possibili eliminare tutti gli assiomi che compaiono nella parte destra di ogni regola semplicemente introducendo un nonterminale:

$S_0\to S$

e poi sostituirlo a tutte le occorrenze dell'assioma.

Costruzione della forma normale senza nonterminali annullabili

L'algoritmo per riportare una grammatica in forma normale senza nonterminali annullabili è rappresentato dai seguenti 4 passi:

• Calcolare l'insieme $null$ che rappresenta un sottoinsieme di $V$ (non terminabili), con la proprietà di essere annullabili;
• Per ogni regola $r\in P$ aggiungere un'alternativa ottenuta eliminando nella parte destra tutti i nonterminali annullabili;
• Rimuovere tutte le regole vuote nella forma $A\to ϵ$ ad eccezione dell'assioma;
• Pulire la grammatica e rimuovere qualsiasi circolarità.

Esempio: Grammatica di partenza:

$S\to SAB|AC$

$A\to aA|\epsilon$

$B\to bB|\epsilon$

$C\to cCc|c$

Grammatica in forma normale:

$S\to SAB|AC|SA|SB|C$

$A\to aA|a$

$B\to bB|b$

$C\to cCc|c$

Copia ed eliminazione di regole

Definiamo un insieme $Copy(A)\subseteq V$ come l'insieme dei non terminali in cui il non terminale $A$ può essere copiato, eventualmente transitivamente:

$Copy(A):=\{B\in V|\mathrm{\exists }\text{ a derivation }A\stackrel{*}{\Rightarrow }B\}$

La computazione di questo insieme può essere eseguita come:

$A\in Copy(A)$

$C\in Copy(A)\text{ if }(B\in Copy(A))\wedge (B\to C\in P)$

Forma normale di Chomsky

Si procede come segue:

• Se la stringa vuota appartiene al linguaggio si aggiunge $S\to \epsilon$ all'insieme delle regole;
• Per ogni regola del tipo $A_0\to A_1{A}_2{A}_3...A_n$:
  • si aggiunga una regola del tipo $A_0\to <A_1><A_2{A}_3...A_n>$ (dove i termini tra parentesi angolari sono nonterminali temporanei)
  • si aggiunga un'altra regola $<A_2{A}_3...A_n>\to A_2{A}_3...A_n$
  • infine se $A_1\in \mathrm{\Sigma }$ si aggiunge $<A_1>\to A_1$

Conversione delle ricorsioni

Questa operazione porta la ricorsione da sinistra a destra, per portare la grammatica nella relativa forma normale. Questa forma normale tornerà utile nel design dei parser top-down.

Spieghiamo con un esempio esplicativo:

Grammatica di partenza:

$A\to A{\beta }_1|A{\beta }_2|...A{\beta }_h$

$A\to {\gamma }_1|{\gamma }_2|...{\gamma }_k$

Si introduce un nuovo non terminale $A^{\prime }$:

$A\to {\gamma }_1|{\gamma }_2|...{\gamma }_k|{\gamma }_1{A}^{\prime }|{\gamma }_2{A}^{\prime }|...{\gamma }_k{A}^{\prime }$

$A^{\prime }\to {\beta }_{1}A|{\beta }_{2}A|...{\beta }_{h}A|{\beta }_1|{\beta }_2|...{\beta }_k$

Non è sempre possibile riportare le grammatiche in questa forma normale.