Linguaggio libero dal contesto
Da Wikipedia, l'enciclopedia libera.
Un linguaggio libero dal contesto (o context-free) è un linguaggio formale accettato da alcuni automi a pila. I linguaggi liberi dal contesto possono essere generati dalle grammatiche libere dal contesto.
[modifica] Esempi
Un archetipo di linguaggio libero dal contesto è 
, il linguaggio di tutte le stringhe di lunghezza pari, di cui la prima metà è composta da a, e la secondà metà da b. Il linguaggio L è generato dalla grammatica 
, ed è accettato dall'automa pushdown M = ({q0,q1,qf},{a},{a,b,z},δ,q0,{qf}) dove δ è definito in questo modo:
δ(q0,a,z) = (q0,a)
δ(q0,b,ax) = (q1,x)
δ(q1,b,ax) = (q1,x)
δ(q1,b,bz) = (qf,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 
. Inoltre, le espressioni aritmetiche sono, a grandi linee, generate da grammatiche liberi dal contesto.
[modifica] 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.
[modifica] 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 |
Grammatiche | Linguaggi | automa minimo |
| Tipo-0 | (illimitato) | Ricorsivamente enumerabile | Macchina di Turing |
| (illimitato) | Ricorsivo | Decider | |
| Tipo-1 | Sensibile al contesto | Sensibile al contesto | Lineare-limitato |
| Tipo-2 | Libero dal contesto | Libero dal contesto | Automa a pila |
| Tipo-3 | Lineare (o Regolare) | Lineare (o Regolare) | A stati finiti |
| Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante. | |||
