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	Libero dal contesto	Libero dal contesto	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.