Quelle est la différence entre les automates finis et les machines à états finis?

16

J'ai utilisé FSM dans les conceptions de circuits séquentiels numériques. Mais je ne connais pas les automates finis. Quelqu'un peut-il m'aider à comprendre la différence «fondamentale» entre les deux?

terminology automata finite-automata gpuguy
la source
5
De Wikipedia : "... Dans la théorie des automates, une branche de l'informatique théorique, un automate déterministe fini (DFA) - également connu sous le nom de machine à états finis déterministe - est une machine à états finis qui accepte / rejette les chaînes finies de symboles et ne produit que un calcul (ou exécution) unique de l'automate pour chaque chaîne d'entrée ... ". DFA est le terme préféré utilisé dans la théorie des automates, FSM est le terme préféré utilisé dans les applications pratiques.
Vor
4
Je pense que FSM est plus inclusif, y compris également les automates Mealy et Moore. Les NFA sont un modèle spécifique.
Raphael
@Raphael: Je suis d'accord avec vous, FSM semble plus large (même wikipedia fait la distinction entre transducteurs, accepteurs, classificateurs et séquenceurs). "DFA" ~ "FSM acceptors" (FSM avec seulement une sortie oui / non) ... en outre, FSM dans les conceptions de circuits, utilise généralement des sorties ... Peut-être pouvez-vous convertir votre commentaire en réponse.
Vor
Personnellement, j'utilise FSM comme un terme large qui inclut les machines DFA, NFA, Mealy et Moore, les transducteurs (à états finis), etc. tout simplement avec un espace d'états fini et sans mémoire auxiliaire.
Dan
1
@Raphael In dans la théorie formelle (ou théorie du calcul), nous préférons utiliser le mot "Automata" - pour souligner que notre machine est une machine "automatique" (se déplaçant automatiquement - comme votre ordinateur) - "automatique" dans le sens où une fois vous avez défini des règles de transition, vous n'avez pas besoin d'appliquer d'intelligent explicite pour traiter / classer les chaînes (il vous suffit de référencer des règles de transition à chaque étape). - alors que le terme machine est préféré dans le contexte de l'appareil (plutôt que du modèle) - bien que les deux soient synonymes l'un de l'autre.
Grijesh Chauhan

Réponses:

12

Autant que je sache, les deux ont des "états" et des "actions" qui font passer la machine d'un état à un autre sur un signal d'entrée. Ainsi, les idées conceptuelles sont les mêmes. Il y a une certaine différence dans les détails.

Dans FSM pour les conceptions de circuits, le signal d'entrée est généralement supposé être un bit (binaire), tandis que dans les automates à états finis, on peut avoir un alphabet général "abstrait" de symboles d'entrée. Deuxièmement, un FSM génère également une sortie, associée à l'état atteint, également binaire. Dans la terminologie des automates, cette «extension» est appelée une machine Moore. Les automates ont cependant des états finaux (ou acceptants), qui signalent une lecture d'entrée favorable. Enfin, les FSM sont principalement déterministes, c'est-à-dire que pour chaque entrée dans un certain état, il y a un état suivant. Dans la théorie des automates, on considère également la variante non déterministe où l'on peut choisir où se déplacer.

Hendrik Jan
la source
6

D'après mon expérience et l'article de Wikipedia, il existe plusieurs types de machines à états finis , notamment

Certaines des notions qui volent diffèrent principalement par la motivation; certains sont issus de la théorie du langage et / ou de la calculabilité, d'autres de l'architecture informatique.

Notez que vous pouvez également modifier plusieurs paradigmes pour obtenir des automates qui sont, sans doute, toujours des automates à états finis, par exemple

Comme vous pouvez le voir, les automates finis vanille tels qu'enseignés dans TCS 101 ne sont qu'une des nombreuses saveurs, chacune avec sa propre définition (plus ou moins formelle).

Raphael
la source
2

Bien que l'idée principale sur laquelle ils s'appuient tous les deux est la même. Les deux utilisent des états finis et passent à un autre état comme flux d'entrée. Cependant, FSM étant une machine, comme l'additionneur complet ou la bascule SR, a des bits en entrée et en sortie. Oui, FSA a également une sortie binaire, 0 pour l'état non final et 1 pour l'état final, mais c'est un mécanisme abstrait et non vu. Il y a une différence dans les digraphes qui sont dessinés pour les représenter. A côté de cela, FSA est un dispositif logique et de calcul tandis que FSM est un dispositif logique numérique.

Saryan Sandeep
la source