Existe-t-il des automates non finis?

35

En théorie des automates, nous lisons tous les automates comme des automates finis, depuis le tout début. Ce que je veux savoir, c'est pourquoi les automates sont-ils finis? Pour être clair, qu'est-ce qui est fini dans un automate - l'alphabet, le langage, les chaînes faites avec des expressions régulières ou quoi? Et existe-t-il (en théorie) des automates non finis?

Parvin
la source
1
Certainement pas le langage ou les "chaînes faites avec des expressions régulières"; de nombreuses expressions rationnelles simples correspondent à un nombre infini de chaînes (mais elles peuvent être reconnues par un automate fini.)
alexis
J'ai posé une question ayant une infinité en tête: cs.stackexchange.com/questions/55864/…
Words Like Jared

Réponses:

34

Tous les modèles d’automates que vous rencontrerez généralement sont représentés avec précision. sinon, ils seraient innombrables, ce qui signifie qu'ils ne sont pas capturés par les modèles complets de Turing. Ou, dans CS-think, ils seraient inutiles¹.

Les "automates finis" sont appelés finis parce qu'ils ont seulement un ensemble fini de configurations (la chaîne en entrée de côté). Les automates à pile, par exemple, ont une pile qui peut avoir un contenu arbitraire - il y a une infinité de configurations possibles.


Nota bene: Les configurations de PDA sont encore représentées! En fait, tout modèle de calcul qui entre dans la calculabilité de Turing doit avoir des configurations finement représentables, sinon les MT ne pourraient pas les simuler.


  1. J'ignore consciemment l'hypercalcul pour les besoins de cette question.
Raphaël
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Raphaël
32

Le nom complet est "automates à états finis". La partie cruciale est que l’état de l’automate puisse être entièrement caractérisé par un élément d’un ensemble fini d’états discrets. Cela signifie que si l'état (pertinent) de l'automate implique une variable à valeur réelle, il existe un nombre infini d'états potentiels (en mettant de côté la finitude des représentations en virgule flottante) et l'automate n'est pas fini.

Cela pourrait ne jamais arriver en informatique théorique, mais ce n’est pas trop exotique dans le domaine de la modélisation de séquences de nombres réels. Les modèles de Markov cachés peuvent être utilisés pour modéliser une séquence de nombres en tant que sortie d'un système probabiliste consistant en un filtre de sortie pour chaque état d'un modèle de Markov (discret, fini) avec des états non observables. Les filtres calculent la sortie à valeur réelle suivante à partir d'un vecteur des sorties précédentes (modèle "autorégressif"), mais le modèle de Markov sous-jacent est fini, car ses probabilités de transition ne dépendent que de l'état de Markov actuel.

Cependant, cet article ( texte intégral ) développe une variante dans laquelle les probabilités de transition dépendent également du vecteur de nombres réels des sorties précédentes. L'état de ce système est la combinaison d'un état de Markov discret et d'un tuple de nombres réels ("modèle de Markov à états mélangés"). Il peut donc s'agir d'un nombre infini d'états différents.

En bref, les automates non finis sont théoriquement bien définis et parfois même rencontrés.

alexis
la source
1
Divulgation complète: Je suis l'un des auteurs du document mentionné. Je ne suis pas sûr que ce soit considéré comme une divulgation appropriée ou une auto-promotion non pertinente ...
alexis
6
Je pense qu'il est parfaitement correct de faire référence à son propre travail, le cas échéant - si vous êtes l'un des principaux experts sur un sujet, nous sommes heureux de vous accueillir! - et une simple divulgation comme la tienne suffit amplement. Merci!
Raphaël
Les automates à états finis n'incluent pas les automates à pile, n'est-ce pas? Y a-t-il une raison particulière jusqu'aux états à nombres réels? Je ne suis pas sûr si je manque quelque chose ici sur la raison pour laquelle cet exemple évident ne fonctionnerait pas ou si vous venez simplement de choisir un exemple inhabituel à la place.
Mehrdad
1
Je pense qu'il essaie de vous demander pourquoi vous n'avez pas utilisé une machine non conventionnelle plus conventionnelle, comme un automate à pile, au lieu de passer à quelque chose comme des variables d'état à valeurs réelles.
user2357112 prend en charge Monica
1
Eh bien, principalement parce que c'est l'exemple auquel j'ai pensé! Mais aussi "l'état" d'un modèle de Markov à états mixtes consiste en un nombre fixe de paramètres, mais il existe toujours un nombre infini d'états (définis comme la position actuelle + probabilités de transition) car certains paramètres sont des nombres réels (mais affectent les transitions, pas seulement la sortie). Dans le cas des PDA, la non-finitude provient de la taille illimitée de la pile; mais il n'y a toujours qu'un nombre fini de règles, qui sont de longueur finie, de sorte qu'à un pas, il n'y a qu'un nombre fini de limites possibles.
alexis
19

Dans un automate fini, il y a un peu de finitude: le nombre d'états, la taille de l'alphabet sous-jacent et la longueur des chaînes acceptées par la machine.

Vous pouvez certainement assouplir la condition de finitude en autorisant, par exemple, la machine à avoir un nombre infini d'états, mais si vous le faites, la machine résultante devient inintéressante, en ce sens que de telles machines peuvent être conçues pour accepter n'importe quelle langue.

Rick Decker
la source
Et si seulement l'alphabet est infini? Et si nous travaillions avec une expression régulière sur des nombres naturels, par exemple? est-ce possible?
Parvin
8
Si l'automate est fini mais l'alphabet est infini, alors l'automate aura un nombre fini de transitions en dehors de chaque état. Tout caractère non associé à l'une des transitions ne sera pas reconnu par l'automate. En conséquence, vous pourriez remplacer l'alphabet infini par un alphabet fini ne contenant que les caractères apparaissant dans les transitions de l'automate, qui accepterait toujours le même langage.
Kevin - Rétablir Monica
3
@parvin Pas vraiment. Vous auriez alors besoin d'un nombre infini de transitions entre vos états (nombre fini), ce que vous ne pouvez toujours pas représenter. Si vous optez pour des prédicats (comme "toutes les entrées paires vont de A à B, toutes les entrées impaires vont de A à C"), vous décomposez votre alphabet en un nombre fini de classes d'équivalence.
Bergi
@ Kevin, cela dépend de la définition du "nombre fini de transitions". Considérons une RTA ordinaire (finie), le prochain état étant choisi en fonction de toute partition finie des nombres naturels: par exemple, le reste de la division par 7. Ou considérons une situation similaire impliquant des nombres réels. Le diagramme d'état est complètement fini, mais il est bien défini sur un alphabet infini.
alexis
@Parvin Je dirais que la réponse est "oui" (voir mon commentaire précédent).
alexis
10

En fait, dans la théorie des automates (qui dérive beaucoup des origines de Kleene, Rabin et Scott), il existe de nombreuses formes d’automates qui ne sont pas finies. Cela se pose pour plusieurs raisons.

Automates à pile , par exemple, sont des automates qui ont un ensemble infini de configurations (celles-ci ont un nombre fini d'états, mais la réalité est qu'elles doivent être considérées comme des «automates infinis»).

Dans le même ordre d'idées, il existe d'autres exemples d'automates infinis pour lesquels l'espace d'états est infini, mais avec beaucoup de structure. Par exemple, on considère la classe des automates qui ont pour espace d'état un espace vectoriel (dimension finie) et comme fonctions de transition des cartes linéaires (plus certaines choses initiales et finales). Celles-ci sont connues sous le nom d' automates pondérés sur un corps de base (dû à Schützenberger en 61). Ceux-ci peuvent être minimisés et testés pour l'égalité. D'autres exemples incluent les automates de registre (ces automates ont un ensemble fini de registres et fonctionnent sur un alphabet infini: ils peuvent comparer des lettres avec des registres et stocker des lettres dans des registres) et la forme plus moderne d' automates nominaux.(qui ont la même expressivité, mais ont de meilleures bases et propriétés). La vacuité de tels automates est décidable.

Mais même pour étudier les automates à états finis, il est logique de parler d'automates infinis. En effet, considérons la catégorie des automates déterministes à états finis qui acceptent un langage donné fixe L, équipé de la notion standard de morphisme d'automate, alors cette catégorie ne peut pas avoir d'objet initial et final. Cependant, si vous vivez dans la catégorie de tous les automates déterministes (disons dénombrables), il existe alors un objet initial (l’automate qui a pour étatsUNE*, comme premier état, le mot vide, quand il lit la lettre une en état vous il va dire vousune, et un état accepte s’il appartient à L). Il y a aussi un objet final (qui a comme langue des états!). L'existence de ces deux objets est un moyen d'expliquer à haut niveau pourquoi les automates déterministes peuvent être minimisés et est étroitement liée à la congruence de Myhill-Nerode.

Pour conclure, il y a des automates infinis, mais les modèles qui sont d'abord étudiés dans une conférence sont toujours ceux à l'état fini.

Thomas Colcombet
la source
2

Je pense que la question suppose la conclusion qu'il n'y a pas d'automates à états infinis quand ils existent, ils ne valent tout simplement pas la peine d'être abordés.

Dans la théorie des automates, il existe une hiérarchie des pouvoirs de différents modèles virtuels. Celui que j'ai appris en avait 4 (dont je me souviens, cela fait un certain temps), celui que j'ai trouvé sur Wikipedia en a 5. Le plus faible dans les automates à états finis et le plus fort sont les machines de Turing. Il existe un certain concept d'un niveau plus puissant que les machines de Turing, que l'on appelle vaguement hypercalcul. De nombreuses descriptions différentes de machines virtuelles entrent dans l'un de ces niveaux. Les machines de Turing sont particulièrement connues pour de nombreux modèles ayant tous le même niveau de puissance de calcul.

Un automate à états infini, au moins un défini formellement, tombera dans l'un de ces niveaux. Il est peut-être intéressant de montrer comment une certaine définition rigoureuse d’un automate à états infinis s’inscrit dans l’un de ces niveaux, mais cela ne serait pas très utile car il existe des machines virtuelles beaucoup mieux étudiées qui représentent chaque niveau. . Cela ressemble à la façon dont il y a peu d'intérêt pour une machine de Turing dotée d'un milliard de bandes, puisqu'elle ne serait pas plus puissante qu'une machine de Turing à bande unique, mais plus compliquée à gérer.

Maintenant, si vous trouviez un automate à états infini qui n’était pas équivalent à un niveau existant de la hiérarchie, cela pourrait être intéressant. Mais sans cela, les automates à états infinis sont déjà capturés dans la hiérarchie existante et, compte tenu des complications supplémentaires associées au traitement de l'infini, nous les évitons simplement de la même manière que nous évitons tout modèle de machine de Turing trop compliqué.

Lawtonfogle
la source
2

La version infinie (naïve) de la machine à états finis déterministe est trop puissante . Une telle chose serait capable de "mémoriser" n'importe quelle langue, de sorte qu'il n'y a pas grand-chose à apprendre à les considérer.

Par exemple, sur un alphabet binaire, considérons un automate sous la forme d'un arbre binaire complet de hauteur infinie. Chaque chaîne possible que vous pouvez considérer comme une entrée correspond uniquement à un nœud de l’arborescence. Vous pouvez donc créer un décideur pour n’importe quelle langue en faisant simplement en sorte que les nœuds correspondants acceptent des états.


la source