Indietro

ⓘ Automa lineare limitato




                                     

ⓘ Automa lineare limitato

Un automa lineare limitato è una particolare macchina di Turing non deterministica in cui la lunghezza del nastro è funzione lineare della dimensione dellinput. Questi automi sono in grado di accettare i linguaggi dipendenti dal contesto generati da grammatiche sensibili al contesto.

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

                                     

1. Grammatiche di Tipo-1

Lunica restrizione posta nelle grammatiche di Tipo-1 è che le regole di produzione siano nella forma α → β {\displaystyle \alpha \rightarrow \beta } con | α | ≤ | β | {\displaystyle \left|\alpha \right|\leq \left|\beta \right|}.

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 dellautoma un nastro più lungo di quello occupato dalla stringa originale.