Utente:Luc4/Sandbox 1

Semplificazione

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

Si dicono simoboli utili simboli per i quali vale la relazione $S{\overset {*}{\Rightarrow }}\alpha X\beta \Rightarrow \omega$. 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 $X{\overset {*}{\Rightarrow }}\left(\omega \in T^{*}\right)$. 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 $S{\overset {*}{\Rightarrow }}\alpha X\beta$. In modo simile alle definizioni precedenti, simboli per i quali non vale la precedente relazione si dicono simboli non raggiungibili.

Eliminazione simboli non generatori

Lemma 1: data una CFG $G=\left(V,T,P,S\right)$, $\exists G'=\left(V',T,P',S\right)$ tale per cui $\forall A\in V',\;A{\overset {*}{\Rightarrow }}\left(\omega \in T^{*}\right)$.
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$\leftarrow \emptyset$
newv$\leftarrow \left\{A:\left(A\rightarrow \omega \right)\in P,\;\omega \in T^{*}\right\}$ 
while oldv$\neq$newv
   oldv$\leftarrow$newv
   newv$\leftarrow oldv\cup \left\{A:\left(A\rightarrow \alpha \right)\in P,\;\alpha \in \left(T\cup oldv\right)^{*}\right\}$
end
V'$\leftarrow$newv
P'$\leftarrow \left\{p\in P:\mathrm {simboli\;in\;p\;tutti} \in \left(V'\cup T\right)\right\}$

Eliminazione delle $\epsilon$-produzioni

Completare.

Eliminazione delle produzioni unitarie

Una produzione unitaria è una produzione del tipo $A\rightarrow B$ con $A,B\in V$. Si dice coppia unitaria una coppia $\left(A,B\right)$ tale per cui $A{\overset {*}{\Rightarrow }}B$ usando solo produzioni unitarie $(A\rightarrow B_{1}\rightarrow B_{2}\rightarrow ...\rightarrow B)$. 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: $\left(A,A\right)$ unitaria $\forall A\in V$.

Ipotesi induttiva: $\left(A,B\right)$ coppia unitaria.

Passo induttivo: $\left(B\rightarrow C\right)\in P\Rightarrow \left(A,C\right)$ coppia unitaria.

Tale algoritmo permette di riconoscere le coppie unitarie. Esse possono quindi essere eliminate dalla grammatica: riconoscendo catene di produzioni unitarie del tipo $A\rightarrow B_{1}\rightarrow B_{2}\rightarrow ...\rightarrow \alpha$ è sufficiente sostituirle con produzioni del tipo $A\rightarrow \alpha$.