# Linguaggi liberi dal contesto (context-free)
## Le limitazioni dei linguaggi regolari

I linguaggi regolari non possono definire (ad esempio) i classici costrutti di programmazione:
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.