Vai al contenuto

Grammatiche: equivalenze, forme normali e trasformazioni

Da Wikiversità, l'apprendimento libero.
lezione
lezione
Grammatiche: equivalenze, forme normali e trasformazioni
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Linguaggi formali e automi
Avanzamento Avanzamento: lezione completa al 100%

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

Equivalenza di due grammatiche[modifica]

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

Due grammatiche e sono debolmente equivalenti se generano lo stesso linguaggio .

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 e 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[modifica]

Vedi la pagina degli esercizi.

Grammatiche in forma normale[modifica]

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
  • grammatica in forma di Chmosky o binaria: le regole della grammatica si presentano solo in due forme:
    • omogenea binaria:
    • terminale con singleton a destra:
  • grammatica in forma real-time: ogni regola inizia con un terminale, cioè ogni regola è nella forma con
  • grammatica in forma di Greibach: ogni regola inizia con un terminale seguito da uno o più non terminali, cioè ogni regola è nella forma con

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[modifica]

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

Espansione di un non terminale[modifica]

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

Diventa:

Eliminazione dell'assioma nella parte destra[modifica]

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

e poi sostituirlo a tutte le occorrenze dell'assioma.

Costruzione della forma normale senza nonterminali annullabili[modifica]

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

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

Esempio: Grammatica di partenza:

Grammatica in forma normale:

Copia ed eliminazione di regole[modifica]

Definiamo un insieme come l'insieme dei non terminali in cui il non terminale può essere copiato, eventualmente transitivamente:

La computazione di questo insieme può essere eseguita come:

Forma normale di Chomsky[modifica]

Si procede come segue:

  • Se la stringa vuota appartiene al linguaggio si aggiunge all'insieme delle regole;
  • Per ogni regola del tipo :
    • si aggiunga una regola del tipo (dove i termini tra parentesi angolari sono nonterminali temporanei)
    • si aggiunga un'altra regola
    • infine se si aggiunge

Conversione delle ricorsioni[modifica]

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:

Si introduce un nuovo non terminale :

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