Automate linéairement borné

En informatique théorique, et en particulier en théorie des automates, un automate linéairement borné (en anglais linear bounded automaton, abrégé en LBA) est une machine de Turing non déterministe qui n'utilise qu'une portion contiguë du ruban de taille linéaire en la taille de l'entrée. Un automate linéairement borné vérifie les trois conditions suivantes : son alphabet d'entrée possède deux symboles particuliers qui servent comme marqueurs de fin à gauche et à droite ; ses transitions ne peuvent écrire sur la bande au-delà des marqueurs de fin ; ses transitions ne peuvent pas déplacer les marqueurs de gauche et de droite au-delà de leur position respectivement à gauche et à droite. Comme pour les machines de Turing, un automate linéairement borné possède une bande composée de cases susceptibles de contenir un symbole pris dans un ensemble fini appelé l'alphabet, une tête peut lire le contenu d'une case et y écrire et peut être déplacée d'une case à la fois, et enfin il possède un nombre fini d'états. À la différence d'une machine de Turing, où la bande est supposée avoir une longueur potentiellement infinie, dans un automate linéairement borné, seule une portion contiguë de la bande, dont la longueur est une fonction linéaire de la longueur de la donnée, est accessible par la tête de lecture et d'écriture. Ce segment est délimité par les cases contenant les marqueurs de fin. Les automates linéairement bornés reconnaissent exactement la classe des langages contextuels. Pour montrer qu'un langage contextuel est reconnu par un automate linéairement borné, on observe que dans une grammaire contextuelle, une étape d'une dérivation allonge toujours le mot produit. Si l'on essaie donc de réduire un mot en l'axiome, chaque étape revient à raccourcir le mot. C'est pourquoi une mémoire bornée suffit. L'argument, dans l'autre sens, est un peu plus long. En 1960, John Myhill introduit un modèle d'automate appelé maintenant automate linéairement borné déterministe.