Automa lineare limitato
Da Wikipedia, l'enciclopedia libera.
Un Automa lineare limitato (abbreviato in inglese LBA) è una forma ristretta di una macchina di Turing non deterministica. Possiede un nastro composto di celle che possono contenere simboli di un alfabeto finito, una testina che può leggere o scrivere una cella sul nastro per volta e può essere mossa e un finito numero di stati. Differisce da una macchina di Turing per il fatto che mentre per la prima il nastro è inizialmente considerato infinito, per la seconda solo una porzione finita e contigua della lunghezza dell'input iniziale che è una funzione lineare può essere acceduto dalla testina di lettura/scrittura. Questa limitazione rende una LBA un modello più accurato di un computer che attualmente esiste che una macchina di Turing in alcuni aspetti.
Gli automi lineari limitati sono accepters per la classe dei linguaggi sensibili al contesto. L'unica restrizione posta nelle grammatiche per tali linguaggi è che le regole di produzione non possono trasformare una stringa in una più corta. 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.
| Teoria degli automi: linguaggi formali e grammatiche formali | |||
|---|---|---|---|
| gerarchia di Chomsky |
Grammatiche | Linguaggi | automa minimo |
| Tipo-0 | (illimitato) | Ricorsivamente enumerabile | Macchina di Turing |
| (illimitato) | Ricorsivo | Decider | |
| Tipo-1 | Sensibile al contesto | Sensibile al contesto | Lineare-limitato |
| Tipo-2 | Context-free | Context-free | Automa a pila |
| Tipo-3 | Lineare (o Regolare) | Lineare (o Regolare) | A stati finiti |
| Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante. | |||
