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.

Esempi

Un archetipo di linguaggio libero dal contesto è $L=\{a^{n}b^{n}:n\geq 1\}$, il linguaggio di tutte le stringhe di lunghezza pari, di cui la prima metà è composta da $a$, e la seconda metà da $b$. Il linguaggio $L$ è generato dalla grammatica $S\to aSb~|~ab$, ed è accettato dall'automa pushdown $M=(\{q_{0},q_{1},q_{f}\},\{a\},\{a,b,z\},\delta ,q_{0},\{q_{f}\})$ dove $\delta$ è definito in questo modo:

$\delta (q_{1},a,z)=(q_{0},a)$
$\delta (q_{2},b,ax)=(q_{1},x)$
$\delta (q_{0},b,ax)=(q_{1},x)$
$\delta (q_{2},b,bz)=(q_{f},z)$

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 $S\to SS~|~(S)~|~\lambda$.
Inoltre, le espressioni aritmetiche sono generate da grammatiche libere dal contesto e non regolari.

Proprietà

• 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.
• Data una grammatica G di tipo 2, è decidibile stabilire se essa genera un linguaggio vuoto ($L(G)=\emptyset$).
• Data una grammatica G di tipo 2, è decidibile stabilire se essa genera un linguaggio infinito.

Bibliografia

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

Voci correlate

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

Altri progetti

Altri progetti

• Wikiversità

• Wikiversità contiene una lezione su linguaggio libero dal contesto

Collegamenti esterni

• Context-free, in Dizionario delle scienze fisiche, Istituto dell'Enciclopedia Italiana, 1996.
• Linguaggio context-free, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.