Apri il menu principale

Linguaggio libero dal contesto

Un linguaggio libero dal contesto (o non contestuale, o context-free) è un linguaggio formale generato da una grammatica che sia, appunto, non contestuale, ovvero tale che le cui regole agiscono su simboli non terminali a prescindere dal contesto in cui essi appaiono.

L'insieme dei linguaggi liberi da contesto è equivalente all'insieme dei linguaggi che sono riconoscibili da un automa a pila non deterministico. La semplicità del tipo di automa necessario al loro riconoscimento e il fatto che lo stesso possa essere generato direttamente dalla definizione della grammatica, rendono tale classe di linguaggi di particolare interesse nell'informatica teorica ed in particolare nella teoria dei linguaggi di programmazione e della loro implementazione.

EsempiModifica

Un archetipo di linguaggio libero dal contesto è  , il linguaggio di tutte le stringhe di lunghezza pari, di cui la prima metà è composta da  , e la seconda metà da  . Il linguaggio   è generato dalla grammatica  , ed è accettato dall'automa pushdown   dove   è definito in questo modo:

 
 
 
 

I linguaggi liberi dal contesto hanno molte applicazioni nei linguaggi di programmazione; per esempio, il linguaggio che verifica che le parentesi siano accoppiate in modo corretto è generato dalla grammatica  .
Inoltre, le espressioni aritmetiche sono generate da grammatiche libere dal contesto e non regolari.[1]

ProprietàModifica

  • La famiglia dei linguaggi liberi dal contesto è chiusa per la concatenazione e l'unione ma non per l'intersezione o la differenza. In ogni caso è chiusa per l'intersezione e la differenza con linguaggi lineari.[2]
  • Data una grammatica G di tipo 2, è decidibile stabilire se essa genera un linguaggio vuoto ( ).[3]
  • Data una grammatica G di tipo 2, è decidibile stabilire se essa genera un linguaggio infinito.[4]

NoteModifica

BibliografiaModifica

  • Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Linguaggi modelli complessità, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1.

Voci correlateModifica

  • Il pumping lemma fornisce delle condizioni necessarie (ma non sufficienti) perché i linguaggi liberi dal contesto siano regolari.

Altri progettiModifica