Linear Bounded Automata

Um autômato linear limitado é uma máquina de Turing não determinística de múltiplas trilhas com uma fita de algum comprimento finito limitado.

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

Aqui,

Memory information ≤ c × Input information

O cálculo é restrito à área constante limitada. O alfabeto de entrada contém dois símbolos especiais que servem como marcadores da extremidade esquerda e da direita, o que significa que as transições não se movem para a esquerda do marcador da extremidade esquerda nem para a direita do marcador da extremidade direita da fita.

Um autômato linear limitado pode ser definido como um 8-tupla (Q, X, ∑, q 0 , ML, MR, δ, F) onde -

  • Q é um conjunto finito de estados

  • X é o alfabeto da fita

  • ∑ é o alfabeto de entrada

  • q0 é o estado inicial

  • ML é o marcador da extremidade esquerda

  • MRé o marcador da extremidade direita onde M R ≠ M L

  • δ é uma função de transição que mapeia cada par (estado, símbolo de fita) para (estado, símbolo de fita, Constante 'c') onde c pode ser 0 ou +1 ou -1

  • F é o conjunto de estados finais

Um autômato limitado linear determinístico é sempre context-sensitive e o autômato linear limitado com linguagem vazia é undecidable..