| dbo:abstract
|
- Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte. On distingue les automates finis non déterministes (abrégés en AFN) en anglais non-deterministic finite automaton ou NFA, des automates finis déterministes (abrégés en AFD) en anglais deterministic finite automata ou DFA. Sans précision supplémentaire, un automate fini est toujours non déterministe, mais on devrait plutôt dire « indéterministe », puisqu'il est indifférent qu'il soit déterministe ou non. Les automates finis (déterministes ou non) reconnaissent exactement des langages rationnels. Ce sont les machines les plus simples dans la hiérarchie de Chomsky, et par conséquent ils sont moins puissants que les automates à pile et, bien entendu, que les machines de Turing. Un automate est constitué d'états et de transitions. Son comportement est dirigé par un mot fourni en entrée : l'automate passe d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. Dans l'exemple ci-dessus, pour l'entrée , et si l'automate démarre en , il passe successivement par les états , le calcul correspondant est : . L'automate est dit « fini » car il possède un nombre fini d'états : il ne dispose donc que d'une mémoire bornée. On peut très bien considérer des automates sans limitation sur le nombre d'états : la théorie qui en résulte est très analogue à la théorie habituelle.Un automate fini peut être vu comme un graphe orienté étiqueté : les états sont les sommets et les transitions sont les arêtes étiquetées. L'état initial est marqué par une flèche entrante ; un état final est, selon les auteurs, soit doublement cerclé (dans la figure 1 ci-dessus, l'état est à la fois initial et final), soit marqué d'une flèche sortante (dans la figure 2 ci-dessous, 1 est initial et 3 est final). Une autre façon commode de représenter un automate fini est sa table de transition. Elle donne, pour chaque état et chaquelettre, l'état d'arrivée de la transition. Voici à droite la table de transition de l'automate de la figure 1 : (fr)
- Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte. On distingue les automates finis non déterministes (abrégés en AFN) en anglais non-deterministic finite automaton ou NFA, des automates finis déterministes (abrégés en AFD) en anglais deterministic finite automata ou DFA. Sans précision supplémentaire, un automate fini est toujours non déterministe, mais on devrait plutôt dire « indéterministe », puisqu'il est indifférent qu'il soit déterministe ou non. Les automates finis (déterministes ou non) reconnaissent exactement des langages rationnels. Ce sont les machines les plus simples dans la hiérarchie de Chomsky, et par conséquent ils sont moins puissants que les automates à pile et, bien entendu, que les machines de Turing. Un automate est constitué d'états et de transitions. Son comportement est dirigé par un mot fourni en entrée : l'automate passe d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. Dans l'exemple ci-dessus, pour l'entrée , et si l'automate démarre en , il passe successivement par les états , le calcul correspondant est : . L'automate est dit « fini » car il possède un nombre fini d'états : il ne dispose donc que d'une mémoire bornée. On peut très bien considérer des automates sans limitation sur le nombre d'états : la théorie qui en résulte est très analogue à la théorie habituelle.Un automate fini peut être vu comme un graphe orienté étiqueté : les états sont les sommets et les transitions sont les arêtes étiquetées. L'état initial est marqué par une flèche entrante ; un état final est, selon les auteurs, soit doublement cerclé (dans la figure 1 ci-dessus, l'état est à la fois initial et final), soit marqué d'une flèche sortante (dans la figure 2 ci-dessous, 1 est initial et 3 est final). Une autre façon commode de représenter un automate fini est sa table de transition. Elle donne, pour chaque état et chaquelettre, l'état d'arrivée de la transition. Voici à droite la table de transition de l'automate de la figure 1 : (fr)
|
| rdfs:comment
|
- Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte. (fr)
- Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte. (fr)
|
