Automates linéaires bornés

Un automate linéaire borné est une machine de Turing non déterministe multipiste avec une bande d'une certaine longueur finie bornée.

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

Ici,

Memory information ≤ c × Input information

Le calcul est limité à la zone délimitée constante. L'alphabet d'entrée contient deux symboles spéciaux qui servent de marqueurs d'extrémité gauche et de marqueurs d'extrémité droite, ce qui signifie que les transitions ne se déplacent ni à gauche du marqueur d'extrémité gauche ni à droite du marqueur d'extrémité droite de la bande.

Un automate linéaire borné peut être défini comme un 8-uplet (Q, X, ∑, q 0 , ML, MR, δ, F) où -

  • Q est un ensemble fini d'états

  • X est l'alphabet de la bande

  • ∑ est l'alphabet d'entrée

  • q0 est l'état initial

  • ML est le marqueur d'extrémité gauche

  • MRest le marqueur d'extrémité droit où M R ≠ M L

  • δ est une fonction de transition qui mappe chaque paire (état, symbole de bande) à (état, symbole de bande, constante 'c') où c peut être 0 ou +1 ou -1

  • F est l'ensemble des états finaux

Un automate borné linéaire déterministe est toujours context-sensitive et l'automate linéaire borné avec un langage vide est undecidable..