Linguaggio libero dal contesto

Un linguaggio libero dal contesto (o context-free) è un linguaggio formale riconosciuto da alcuni automi a pila. I linguaggi liberi dal contesto possono essere generati dalle grammatiche libere dal contesto.

Esempi

Un archetipo di linguaggio libero dal contesto è $L = \{a^nb^n:n\geq1\}$, 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à di chiusura

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.

Voci correlate

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

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.

Portale Informatica

Portale Matematica