Linguaggi liberi dal contesto (context-free)

Le limitazioni dei linguaggi regolari

I linguaggi regolari non possono definire (ad esempio) i classici costrutti di programmazione:

BEGIN
  BEGIN
    ...
  END
END

perché non possono imporre (nel caso indicato sopra) che il numero di BEGIN sia pari al numero di END (l'unico modo sarebbe $(be)^{*}$ ma questo non permette l'annidamento).

In questa lezione vedremo come definire linguaggi grazie a grammatiche non contestuali, dette anche di tipo 2.

Grammatiche libere dal contesto (Context-Free)

Una grammatica context-free è definita da 4 componenti:

• Alfabeto non terminale (indicato con $V$)
• Alfabeto terminale (indicato con $\Sigma$)
• Insieme di regole (indicato con $P$)
  • Una regola è una coppia ordinata così definita: $(X,\alpha )\ |\ X\in V,\ \alpha \in (V\cup \Sigma )^{*}$
• Un assioma (indicato con $S\in V$)

Per non creare ambiguità, precisiamo inoltre:

• Non utilizzeremo mai i metasimboli $\to ,I,\cup ,\epsilon$ in nessun alfabeto;
• $V\cap \Sigma =\varnothing$.

Per abbreviazione possiamo condensare le regole con gli stessi simboli non-terminali con la seguente notazione:

$X\to \alpha _{1},X\to \alpha _{2},...,X\to \alpha _{n}$

$X\to \alpha _{1}|\alpha _{2}|...|\alpha _{n}$ oppure $X\to \alpha _{1}\cup \alpha _{2}\cup ...\cup \alpha _{n}$

Diverse notazioni possono essere usate per i simboli terminali e non terminali, tra cui:

• grassetto: $a\to {\textbf {a}}|{\textbf {b}}|c$
• parentesi angolari: $\langle a\rangle \to a|b|\langle c\rangle$
• apici: $a\to 'a'|'b'|c$
• maiuscolo-minuscolo: $F\to a|b|C$

noi utilizzeremo quest'ultima, quindi:

• caratteri terminali: lettere minuscole ($a,b,c,...$)
• caratteri non terminali: lettere maiuscole ($A,B,C,...$)
• stringhe terminali ($\in \Sigma$): (lettere minuscole da s $r,s,...,z$)
• stringhe non terminali ($\in V^{*}$): (lettera sigma minuscola $\sigma _{1},\sigma _{2},...$)
• stringhe miste ($\in (V\cup \Sigma )^{*}$): lettere greche ($\alpha ,\beta ,\gamma ,...$)

Relazione di derivazione

Definiamo un operatore o relazione di derivazione:

per $\beta ,\gamma \in (V\cup \Sigma )^{*}$ diciamo che $\beta$ deriva $\gamma$ per una grammatica $G$ (e lo scriviamo come $\beta \ {\underset {G}{\Rightarrow }}\ \gamma$) se e solo se:

• $\exists \alpha \in (V\cup \Sigma )^{*}$ t.c. $A\to \alpha$ è una regola di $G$, e
• $\beta =\sigma A\eta$, e
• $\gamma =\sigma \alpha \eta$

In questo caso diciamo anche che $\alpha$ riduce a $A$.

Similmente alle grammatiche regolari possiamo scrivere le chiusure:

• rispetto alla potenza: $\beta \ {\overset {n}{\underset {G}{\Rightarrow }}}\ \gamma$
• transitiva e riflessiva: $\beta \ {\overset {*}{\underset {G}{\Rightarrow }}}\ \gamma$
• transitiva non riflessiva: $\beta \ {\overset {+}{\underset {G}{\Rightarrow }}}\ \gamma$

Altre definizioni:

• chiamiamo $\alpha \in (V\cup \Sigma )^{*}$ stringa generata da G se $A\ {\overset {*}{\underset {G}{\Rightarrow }}}\ \alpha$
• chiamiamo $s\in \Sigma ^{*}$ frase o proposizione se $A\ {\overset {*}{\underset {G}{\Rightarrow }}}\ s$

Produzione

Introduciamo un'altra relazione tra non terminali chiamata produzione:

Un nonterminale $A$ produce un nonterminale $B$ se e solo se $A\to \alpha B\beta$ con $\alpha ,\beta \in (V\cup \Sigma )^{*}$

Linguaggi liberi dal contesto (Context-Free)

Un linguaggio libero dal contesto (o per brevità context-free o free) è un linguaggio generato da una grammatica context-free:

$L(G)=\{\ x|x\in \Sigma ^{*}|S{\overset {+}{\underset {G}{\Rightarrow }}}x\}$

un linguaggio può anche non essere definito a partire dall'assioma, ma anche a partire da qualsiasi non terminale, in questo caso scriviamo:

$L_{A}(G)=\{\ x|x\in \Sigma ^{*}|A{\overset {+}{\underset {G}{\Rightarrow }}}x\}$

Equivalenza di grammatiche

Diciamo che due grammatiche sono uguali se generano lo stesso linguaggio:

$L(G)=L(G')$

(per la definizione di equivalenza di linguaggi si veda la relativa lezione)

Grammatiche errate e regole non utili

Una grammatica non errata deve ovviamente avere tutti i non terminali definiti. Inoltre non dovrebbe contenere non terminali ch enon sono utili al fine di generare il linguaggio (perché ad esempio irraggiungibili).

Una grammatica è pulita o ridotta se e solo se entrambe le condizioni seguenti sono valide:

• Qualsiasi non terminale $A$ è raggiungibile dall'assioma, cioè se esiste una derivazione:

$S{\overset {*}{\Rightarrow }}\alpha A\beta$

• Qualsiasi non terminale $A$ è definito, cioè genera sempre un linguaggio non vuoto:

$L_{A}(G)\neq \varnothing$

Nel secondo punto è compreso anche il caso in cui la derivazione non termini (numero di sostituzioni necessarie infinito), ad esempio: $\{S\to AA,\ A\to bS\}$

Pulizia di grammatiche (Grammar cleaning)

Qui presentiamo l'algoritmo necessario a pulire le grammatiche, cioè riportarle a rispettare le condizioni enunciate nella lezione precedente. L'algoritmo è composto da due fasi: Fase 1: costruire l'insieme $UNDEF$, con la lista dei nonterminali non definiti

• Il modo migliore per costruire $UNDEF$ è calcolarlo come il complemento di nontermiali definiti: $DEF=V\backslash UNDEF$ quindi $UNDEF=\neg DEF$. $DEF$ può essere facilmente costruito utilizzando una definizione ricorsiva:

$DEF:=\{\ A|(A\to u)\in P,{\text{ with }}u\in \Sigma ^{*}\ \}$

$DEF:=DEF\cup \{\ B|(B\to D_{1}D_{2}D_{3}...D_{n})\in P\ \land \ \forall i(D_{i}\in DEF\cup \Sigma )\}$

ad ogni iterazione verifichiamo la presenza o meno di nuovi nonterminali. Per ogni nuovo nonterminale trovato, verifichiamo tutta la parte a destra: aggiungiamo il terminale trovato a DEF se tutti gli elementi della parte a destra sono definiti.

Infine calcoliamo con il complemento UNDEF da DEF, ed eliminiamo tutti i nonterminali.

Fase 2: costruire l'insieme dei terminali irraggiungibili

Costruiamo il grafo delle produce-relazioni, e diciamo che C è raggiungibile se esiste un percorso S-C nel grafo. I nodi isolati o sorgente, vengono eliminati (ad eccezione degli assiomi ovviamente).

Inoltre vogliamo anche eliminare le derivazioni circolari che introducono ambiguità (osservando sempre il grafo in cerca di cicli).

Linguaggi ricorsivi e infiniti

Una grammatica $G$ è ricorsiva se è presente almeno una relazione del tipo:

$A{\overset {n}{\underset {G}{\Rightarrow }}}xAy$

se inoltre $n=1$ la grammatica è detta immediatamente ricorsiva. $A$ è il non terminale ricorsivo, mentre se $x=\varepsilon$ la regola è detta ricorsiva a sinistra e se $y=\varepsilon$ la regola è detta ricorsiva a destra.

N.B. una grammatica ricorsiva non è necessariamente circolare!

Condizione necessaria e sufficiente affinché un linguaggio $L(G)$ sia infinito:

• $G$ pulita e senza derivazioni circolari, e
• $G$ contiene almeno una regola ricorsiva

Esempio

Esempio 1 Sia data la seguente grammatica:

$S\to aBc$

$B\to ab\ |\ Ca$

$C\to c\ |\ \varepsilon$

Si nota subito che non ci sono relazioni ricorsive (costruendo il grafo S->B->C), per questo il linguaggio è finito.

Esempio 2 Sia data la seguente grammatica:

$A\to AaB\ |\ B$

$B\to BbC\ |\ C$

$C\to cAc\ |\ d$

Il linguaggio è evidentemente ricorsivo (cicli A->A, B->B, A->B->C->A). Non è però circolare: posso sempre sostituire A con B e sempre B con C e quest'ultimo con un simbolo terminale (d).

Composizione di linguaggi liberi

Applicando l'unione, la concatenzione e l'operazione stella di Kleene a un linguaggio libero dal contesto, si ottiene un linguaggio libero dal contesto. Quindi:

La famiglia dei linguaggi liberi dal contesto è chiusa rispetto alle operazioni di unione, concatenzione e star di Kleene.

Di conseguenza sarà chiuso anche per l'operatore di cross (+).

In particolare prese due grammatiche:

$G_{1}=(\Sigma _{1},V_{N_{1}},P_{1},S_{1})\quad G_{2}=(\Sigma _{2},V_{N_{2}},P_{2},S_{2})$ con $V_{N_{1}}\cap V_{N_{2}}=\varnothing$ e $S\notin (V_{N_{1}}\cup V_{N_{2}})$

• unione: $G=(\Sigma _{1}\cup \Sigma _{2},V_{N_{2}}\cup V_{N_{1}}\cup S,P_{1}\cup P_{2}\cup \{S\to S_{1}|S_{2}\},\{S\})$
• concatenazione: $G=(\Sigma _{1}\cup \Sigma _{2},V_{N_{2}}\cup V_{N_{1}}\cup \{S\},P_{1}\cup P_{2}\cup \{S\to S_{1}S_{2}\},S)$
• star: $G_{1}=(\Sigma _{1},V_{N_{1}},P_{1}\cup \{S\to SS_{1}|\varepsilon \},S)$

N.B: l'intersezione di linguaggi free non garantisce che il risultato sia free.

Generare una grammatica libera da un'espressione regolare

In questa sezione vedremo com'è possibile ottenere da un'espressione regolare la corrispondente grammatica context-free. I linguaggi regolari sono anche linguaggi liberi, ma non viceversa: $REG\subset LIB$ ($REG\not \equiv LIB$)

La tabella sottostante mostra le regole di conversione delle RE in regole di grammatica (ipotizzando regole nella forma $R\to ...$:

RE	Grammatica (parte destra)
$r=r_{1}\cdot r_{2}\cdot ...\cdot r_{k}$	$E_{1}E_{2}...E_{k}$
$r=r_{1}\cup r_{2}\cup ...\cup r_{k}$	$E_{1}|E_{2}|...|E_{k}$
$r=(r_{1})^{*}$	$EE_{1}\ |\ \varepsilon$ oppure $E_{1}E\ |\ \varepsilon$
$r=(r_{1})^{+}$	$EE_{1}\ |\ E_{1}$ oppure $E_{1}E\ |\ E_{1}$
$r=b\in \Sigma$	$b$
$r=\varepsilon$	$\varepsilon$

Esempio

Trasformiamo la RE

$E=(abc)^{+}d\cup e^{*}$

nella grammatica:

$E\to E_{1}|E_{2}$

$E_{1}\to E_{3}E_{4}$

$E_{3}\to E_{3}E_{5}|E_{5}$

$E_{4}\to d$

$E_{5}\to abc$

$E_{2}\to E_{2}E_{6}|\varepsilon$

$E_{6}\to e$

Limiti dei linguaggi liberi

I linguaggi liberi presentano però dei problemi: non tutti i linguaggi possono essere generati a partire da una grammatica libera. Si consideri ad esempio due casi molto diffusi:

$L=\{a^{n}b^{n}c^{n}\ |\ n\geq 1\ \}$

$L=\{uu\ |\ u\in \Sigma ^{+}\}$

questi linguaggi non sono liberi.

Altri progetti

Altri progetti

Wikipedia

• Wikipedia contiene informazioni su Linguaggi liberi dal contesto