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. DescriptionUn automate linéairement borné vérifie les trois conditions suivantes :
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. Automates linéairement bornés et langages contextuelsLes 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. HistoireEn 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]. Deux problèmes sur les automates linéairement bornésDans son article fondateur, Kuroda pose deux problèmes de recherche qui sont devenus célèbres sous le nom anglais LBA problems.
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. Notes et référencesBibliographie
Liens externes
Source de la traduction
|
Portal di Ensiklopedia Dunia