Indietro

ⓘ Linguaggio libero dal contesto




Linguaggio libero dal contesto
                                     

ⓘ Linguaggio libero dal contesto

Un linguaggio libero dal contesto è 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.

Linsieme dei linguaggi liberi da contesto è equivalente allinsieme 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 nellinformatica teorica ed in particolare nella teoria dei linguaggi di programmazione e della loro implementazione.

                                     

1. Esempi

Un archetipo di linguaggio libero dal contesto è L = { a n b n: n ≥ 1 } {\displaystyle 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 {\displaystyle a}, e la seconda metà da b {\displaystyle b}. Il linguaggio L {\displaystyle L} è generato dalla grammatica S → a S b | a b {\displaystyle S\to aSb~|~ab}, ed è accettato dallautoma pushdown M = {\displaystyle M=\{q_{0},q_{1},q_{f}\},\{a\},\{a,b,z\},\delta,q_{0},\{q_{f}\}} dove δ {\displaystyle \delta } è definito in questo modo:

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 → S | S | λ {\displaystyle S\to SS~|~S~|~\lambda }. Inoltre, le espressioni aritmetiche sono generate da grammatiche libere dal contesto e non regolari.

                                     

2. Proprietà

  • La famiglia dei linguaggi liberi dal contesto è chiusa per la concatenazione e lunione ma non per lintersezione o la differenza. In ogni caso è chiusa per lintersezione e la differenza con linguaggi lineari.
  • Data una grammatica G di tipo 2, è decidibile stabilire se essa genera un linguaggio infinito.
  • Data una grammatica G di tipo 2, è decidibile stabilire se essa genera un linguaggio vuoto L G = ∅ {\displaystyle LG=\emptyset }).