Linguaggio libero dal contesto

Da Wikipedia, l'enciclopedia libera.

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

Esempi[modifica | modifica sorgente]

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.[1]

Proprietà di chiusura[modifica | modifica sorgente]

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.

Note[modifica | modifica sorgente]

  1. ^ http://www.cs.odu.edu/~toida/nerzic/390teched/regular/reg-lang/non-regularity.html

Bibliografia[modifica | modifica sorgente]

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

Voci correlate[modifica | modifica sorgente]

  • 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 formale 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 proprio della categoria immediatamente sottostante.