Automa lineare limitato

Un automa lineare limitato (in inglese linear bounded automata, LBA) è una particolare macchina di Turing non deterministica in cui la lunghezza del nastro è funzione lineare della dimensione dell'input.[1] Questi automi sono in grado di accettare i linguaggi dipendenti dal contesto generati da grammatiche sensibili al contesto (o di Tipo-1 secondo la gerarchia di Chomsky).[2][3]

Come una macchina di Turing, il nastro di un LBA è composto da celle che possono contenere simboli appartenenti ad un alfabeto finito. L'automa possiede un numero finito di stati e la sua testina può leggere e scrivere una sola cella per volta.

Grammatiche di Tipo-1 modifica

  Lo stesso argomento in dettaglio: Grammatica dipendente dal contesto.

L'unica restrizione posta nelle grammatiche di Tipo-1 è che le regole di produzione siano nella forma   con  .

Quindi nessuna derivazione di una stringa in linguaggio sensibile al contesto può contenere una forma sentenziale più lunga della stringa stessa. Dal momento che c'è una corrispondenza uno ad uno tra gli automi lineari limitati e queste grammatiche, non si necessita per il riconoscimento della stringa da parte dell'automa un nastro più lungo di quello occupato dalla stringa originale.

Note modifica

  1. ^ Academic Press Dictionary of Science and Technology.
  2. ^ (EN) Formal languages, in Encyclopedia of Computer Science, Hoboken, Wiley, 2003.
  3. ^ (EN) Chomsky hierarchy, in Encyclopedia of Computer Science, Hoboken, Wiley, 2003.

Bibliografia modifica

  • (EN) linear bounded automaton, in Academic Press Dictionary of Science and Technology, Oxford, Elsevier Science & Technology, 1992.
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 sovrastante.