Linguaggio libero dal contesto

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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à[modifica | modifica wikitesto]

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

Note[modifica | modifica wikitesto]

  1. ^ http://www.cs.odu.edu/~toida/nerzic/390teched/regular/reg-lang/non-regularity.html
  2. ^ Ausiello, 2003, pp. 136-138
  3. ^ Ausiello, 2003, pp. 138
  4. ^ Ausiello, 2003, pp. 139

Bibliografia[modifica | modifica wikitesto]

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

Voci correlate[modifica | modifica wikitesto]

  • 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.