Utente:Luc4/Sandbox 1

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

Semplificazione

[modifica | modifica wikitesto]

E' possibile semplificare grammatiche libere dal contesto al fine di ottenere definizioni più semplici delle stesse. L'operazione di semplificazione si compone di una sequenza di passi successivi.

Eliminazione dei simboli inutili

[modifica | modifica wikitesto]

Si dicono simoboli utili simboli per i quali vale la relazione . Simboli che non siano utili si dicono simboli inutili. L'eliminazione di tali simboli può avvenire tramite l'eliminazione successiva, in questo ordine, di simboli non generatori e simboli non raggiungibili. Simboli generatori sono simboli per i quali vale la relazione . Simboli non generatori sono simboli per i quali non vale la relazione precedente. Simboli raggiungibili sono invece tutti i simboli X per i quali vale la relazione . In modo simile alle definizioni precedenti, simboli per i quali non vale la precedente relazione si dicono simboli non raggiungibili.

Eliminazione simboli non generatori

[modifica | modifica wikitesto]

Lemma 1: data una CFG , tale per cui .
Il lemma 1 ci garantisce l'esistenza di una grammatica priva di simboli non generatori. L'algoritmo per l'eliminazione di questi simboli viene riportato di seguito:

oldv
newv 
while oldvnewv
   oldvnewv
   newv
end
V'newv
P'

Eliminazione simboli non raggiungibili

[modifica | modifica wikitesto]

Eliminazione delle -produzioni

[modifica | modifica wikitesto]

Completare.

Eliminazione delle produzioni unitarie

[modifica | modifica wikitesto]

Una produzione unitaria è una produzione del tipo con . Si dice coppia unitaria una coppia tale per cui usando solo produzioni unitarie . Esiste un algoritmo che permette di individuare tali coppie nella grammatica e di eliminarle al fine di ottenerne una versione che non contenga produzioni unitarie. Tale algoritmo può essere definito per induzione.

Base: unitaria .
Ipotesi induttiva: coppia unitaria.
Passo induttivo: coppia unitaria.

Tale algoritmo permette di riconoscere le coppie unitarie. Esse possono quindi essere eliminate dalla grammatica: riconoscendo catene di produzioni unitarie del tipo è sufficiente sostituirle con produzioni del tipo .