Linguaggi liberi dal contesto (context-free)

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