Automi delimitati lineari

Un automa lineare limitato è una macchina di Turing non deterministica multitraccia con un nastro di una certa lunghezza finita limitata.

Length = function (Length of the initial input string, constant c)

Qui,

Memory information ≤ c × Input information

Il calcolo è limitato all'area delimitata costante. L'alfabeto di input contiene due simboli speciali che fungono da marker di estremità sinistra e marker di estremità destra, il che significa che le transizioni non si spostano né a sinistra del marker di estremità sinistra né a destra del marker di estremità destra del nastro.

Un automa lineare limitato può essere definito come una tupla di 8 (Q, X, ∑, q 0 , ML, MR, δ, F) dove -

  • Q è un insieme finito di stati

  • X è l'alfabeto del nastro

  • ∑ è l'alfabeto di input

  • q0 è lo stato iniziale

  • ML è il marcatore dell'estremità sinistra

  • MRè il marker dell'estremità destra dove M R ≠ M L

  • δ è una funzione di transizione che mappa ogni coppia (stato, simbolo del nastro) su (stato, simbolo del nastro, costante 'c') dove c può essere 0 o +1 o -1

  • F è l'insieme degli stati finali

Un automa lineare limitato deterministico è sempre context-sensitive e l'automa lineare limitato con linguaggio vuoto è undecidable..