Linguaggi liberi dal contesto (context-free)
Le limitazioni dei linguaggi regolari
modificaI 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 ma questo non permette l'annidamento).
In questa lezione vedremo come definire linguaggi grazie a grammatiche non contestuali, dette anche di tipo 2[1].
Grammatiche libere dal contesto (Context-Free)
modificaUna grammatica context-free è definita da 4 componenti[1]:
- Alfabeto non terminale (indicato con )
- Alfabeto terminale (indicato con )
- Insieme di regole (indicato con )
- Una regola è una coppia ordinata così definita:
- Un assioma (indicato con )
Per non creare ambiguità, precisiamo inoltre:
- Non utilizzeremo mai i metasimboli in nessun alfabeto;
- .
Per abbreviazione possiamo condensare le regole con gli stessi simboli non-terminali con la seguente notazione:
- oppure
Diverse notazioni possono essere usate per i simboli terminali e non terminali, tra cui:
- grassetto:
- parentesi angolari:
- apici:
- maiuscolo-minuscolo:
noi utilizzeremo quest'ultima, quindi:
- caratteri terminali: lettere minuscole ( )
- caratteri non terminali: lettere maiuscole ( )
- stringhe terminali ( ): (lettere minuscole da s )
- stringhe non terminali ( ): (lettera sigma minuscola )
- stringhe miste ( ): lettere greche ( )
Relazione di derivazione
modificaDefiniamo un operatore o relazione di derivazione:
- per diciamo che deriva per una grammatica (e lo scriviamo come ) se e solo se:
- t.c. è una regola di , e
- , e
In questo caso diciamo anche che riduce a .
Similmente alle grammatiche regolari possiamo scrivere le chiusure:
- rispetto alla potenza:
- transitiva e riflessiva:
- transitiva non riflessiva:
Altre definizioni:
- chiamiamo stringa generata da G se
- chiamiamo frase o proposizione se
Produzione
modificaIntroduciamo un'altra relazione tra non terminali chiamata produzione:
- Un nonterminale produce un nonterminale se e solo se con
Linguaggi liberi dal contesto (Context-Free)
modificaUn linguaggio libero dal contesto (o per brevità context-free o free) è un linguaggio generato da una grammatica context-free:
un linguaggio può anche non essere definito a partire dall'assioma, ma anche a partire da qualsiasi non terminale, in questo caso scriviamo:
Equivalenza di grammatiche
modificaDiciamo che due grammatiche sono uguali se generano lo stesso linguaggio:
(per la definizione di equivalenza di linguaggi si veda la relativa lezione)
Grammatiche errate e regole non utili
modificaUna 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 è raggiungibile dall'assioma, cioè se esiste una derivazione:
- Qualsiasi non terminale è definito, cioè genera sempre un linguaggio non vuoto:
Nel secondo punto è compreso anche il caso in cui la derivazione non termini (numero di sostituzioni necessarie infinito), ad esempio:
Pulizia di grammatiche (Grammar cleaning)
modificaQui 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 , con la lista dei nonterminali non definiti
- Il modo migliore per costruire è calcolarlo come il complemento di nontermiali definiti: quindi . può essere facilmente costruito utilizzando una definizione ricorsiva:
- 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
modificaUna grammatica è ricorsiva se è presente almeno una relazione del tipo:
se inoltre la grammatica è detta immediatamente ricorsiva. è il non terminale ricorsivo, mentre se la regola è detta ricorsiva a sinistra e se la regola è detta ricorsiva a destra.
N.B. una grammatica ricorsiva non è necessariamente circolare!
Condizione necessaria e sufficiente affinché un linguaggio sia infinito:
- pulita e senza derivazioni circolari, e
- contiene almeno una regola ricorsiva
Dimostrazione
modificaEsempio
modificaEsempio 1 Sia data la seguente grammatica:
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:
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
modificaApplicando 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:
- con e
- unione:
- concatenazione:
- star:
N.B: l'intersezione di linguaggi free non garantisce che il risultato sia free.
Generare una grammatica libera da un'espressione regolare
modificaIn 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: ( )
La tabella sottostante mostra le regole di conversione delle RE in regole di grammatica (ipotizzando regole nella forma :
RE | Grammatica (parte destra) |
---|---|
oppure | |
oppure | |
Esempio
Trasformiamo la RE
nella grammatica:
Limiti dei linguaggi liberi
modificaI 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:
questi linguaggi non sono liberi.
Altri progetti
modifica- Wikipedia contiene informazioni su Linguaggi liberi dal contesto
Note
modifica- ↑ 1,0 1,1 Si invita, prima di procedere, a ripassare le lezioni di Informatica teorica relative alle classificazioni delle grammatiche e al loro uso