Automate linéairement borné

Un automate linéairement borné vérifie les trois conditions suivantes :

1. son alphabet d'entrée possède deux symboles particuliers qui servent comme marqueurs de fin à gauche et à droite ;
2. ses transitions ne peuvent écrire sur la bande au-delà des marqueurs de fin ;
3. 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[1]. Peu de temps après, Lawrence Landweber prouve que les langages reconnus par les automates linéairement bornés déterministes sont contextuels[2]. En 1964, Sige-Yuki Kuroda introduit le modèle plus général d'automate linéairement borné (non déterministe) tel que décrit plus haut et a prouvé qu'ils acceptent exactement les langages contextuels[3].

Dans son article fondateur, Kuroda pose deux problèmes de recherche qui sont devenus célèbres sous le nom anglais LBA problems.

• Le premier problème est de déterminer si la classe des langages acceptés par les automates linéairement bornés coïncide avec la classe des automates linéairement bornés déterministes. En d'autres termes, est-ce que tout langage contextuel peut être accepté par un automate linéairement borné déterministe ? En termes de complexité algorithmique, ce problème s'énonce

A-t-on l'égalité : NSPACE(O(n)) = DSPACE(O(n)) ou, avec d'autres notations, NLIN-SPACE = LIN-SPACE ?

• Le deuxième problème est de déterminer si la classe des langages reconnus par les automates linéairement bornés est fermée par complémentation. En termes de complexité algorithmique, ce problème s'énonce

A-t-on l'égalité : NSPACE(O(n)) = co-NSPACE(O(n)) ?

Déjà Kuroda a remarqué qu'une réponse négative au deuxième problème aurait entraîné une réponse négative au premier. Mais en fait, le deuxième problème a une réponse positive. Ceci est une conséquence du théorème d'Immerman-Szelepcsényi reliant les classes NSPACE et co-NSPACE. Ce résultat, prouvé indépendamment par Neil Immerman[4] et Róbert Szelepcsényi[5] en 1987, leur a valu le prix Gödel en 1995. En ce qui concerne le premier problème, il est, en 2010, toujours ouvert.

• John Myhill, « Linearly Bounded Automata », WADD Technical Note 60-165, Wright-Patterson Air Force Base, Wright Air Development Division, Ohio, June 1960.
• Peter S. Landweber, « Three Theorems on Phrase Structure Grammars of Type 1 », Information and Computation 6(2), pp. 131-136 (1963)
• Sige-Yuki Kuroda, « Classes of Languages and Linear-Bounded Automata », Information and Computation, 7(2), pp. 207–223 (1964)
• N. Immerman, Nondeterministic Space is Closed under Complementation, SIAM Journal on Computing 17, 1988, pp. 935–938.
• R. Szelepcsényi, The Method of Forcing for Nondeterministic Automata, Bulletin of the EATCS 33, 1987, pp. 96–100 et Acta Informatica 26(3), pp. 279-284 (1988)

• Linear Bounded Automata by Forbes D. Lewis
• Linear Bounded Automata slides, part of Context-sensitive Languages by Arthur C. Fleck
• Linear-Bounded Automata , part of Theory of Computation syllabus, by David Matuszek

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Linear bounded automata » (voir la liste des auteurs).