Linguaggi liberi dal contesto (context-free)

Da Wikiversità, l'apprendimento libero.
lezione
lezione
Linguaggi liberi dal contesto (context-free)
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Linguaggi formali e automi
Avanzamento Avanzamento: lezione completa al 75%

Le limitazioni dei linguaggi regolari[modifica]

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 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)[modifica]

Una 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[modifica]

Definiamo 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[modifica]

Introduciamo un'altra relazione tra non terminali chiamata produzione:

Un nonterminale produce un nonterminale se e solo se con

Linguaggi liberi dal contesto (Context-Free)[modifica]

Un 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[modifica]

Diciamo 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[modifica]

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 è 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)[modifica]

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 , 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[modifica]

Una 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[modifica]

Esempio[modifica]

Esempio 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[modifica]

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:

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[modifica]

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: ()


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[modifica]

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:

questi linguaggi non sono liberi.

Altri progetti[modifica]

Note[modifica]

  1. 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