Automate fini

Pour les articles homonymes, voir Automate.

Fig. 1 : Automate fini reconnaissant les écritures binaires des multiples de 3.

Un automate fini (on dit parfois, par une traduction littérale maladroite de l'anglais machine à états finis au lieu de machine avec un nombre fini d'états), en anglais 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.

Les automates finis 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 $1010010$ , et si l'automate démarre en $s 0$ , il passe successivement par les états $s 0 s 1 s 2 s 2 s 1 s 2 s 2 s 1$ , le calcul correspondant est

$s_0\xrightarrow1s_1\xrightarrow0s_2\xrightarrow1s_2\xrightarrow0s_1\xrightarrow0s_2\xrightarrow1s_2\xrightarrow0s_1$ .

Table de transition
$\begin{array}{c\|cc} &0&1\\\hline s_0&s_0&s_1\\ s_1&s_2&s_0\\ s_2&s_1&s_2 \end{array}$

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é (figure 1 ci-dessus), soit marqué d'une flèche sortante (figure 2 ci-dessous).

Une autre façon commode de représenter un automate fini est sa table de transition. Elle donne, pour chaque état et chaque lettre, l'état d'arrivée de la transition. Voici à droite la table de transition de l'automate de la figure 1 :

Aperçu

Il existe plusieurs types d'automates finis. Les « accepteurs » ou « reconnaisseurs » produisent en sortie une réponse « oui » ou « non », selon qu'ils acceptent (oui) ou rejettent (non) le mot présenté en entrée. Dans l'exemple ci-dessus, le mot $1010010$ n'est pas accepté, mais le mot $10100100$ est accepté. D'autres automates classent l'entrée par catégorie: au lieu de répondre par oui ou par non, ils répondent par une classification; de tels automates se rencontrent par exemple en linguistique. Les automates pondérés (weighted automata^[1] en anglais) associent à chaque mot une valeur numérique.

Les automates finis servent à caractériser des langages (c'est-à-dire, des ensembles de mots finis en général): ce sont les langages composés des mots acceptés, ou langages reconnus par les automates. Des extensions des automates finis reconnaissent des langages de mots infinis. Ce sont(les automates sur les mots infinis; les plus connus d'entre eux sont les automates de Büchi), les automates de Rabin et les automates de Muller. D'autres automates reconnaissent divers types d'arbres (automates d'arbres).

Une sous-catégorie importante est celle des automates déterministes (les automates généraux sont parfois appelés non déterministes [il conviendrait mieux de les qualifier de « indéterministes »]). Un automate est déterministe si, pour chacun de ses états, il y a au plus une transition pour chaque étiquette possible et si, de plus, il a un seul état initial. S'il a exactement une transition par étiquette, on parle alors d'automate déterministe complet. L'automate ci-dessus est déterministe et complet.

Dans les automates non déterministes, il peut y avoir plusieurs transitions à partir d'un état donné pour une étiquette donnée. Ici, le terme « non déterministe » ne signifie pas la négation de « déterministe » mais l'absence éventuelle de cette propriété.

Il est remarquable que tout automate fini peut être transformé, au moyen d'une opération qui peut éventuellement augmenter exponentiellement son nombre d'états, en un automate déterministe: c'est la déterminisation expliquée plus loin.

Les automates finis se rencontrent, dans une formulations proche, dans les circuits intégrés numériques, où l'entrée, l'état et le résultat sont des vecteurs de bits de taille fixe. Les machines de Moore et machines de Mealy sont des automates finis avec sortie. Dans les machines de Mealy, les actions (sorties) sont liées aux transitions, tandis que dans les machines de Moore, les actions sont liées aux états. Les transducteurs finis sont des automates avec sortie plus généraux.

Définitions formelles

Automate fini

Fig. 2 : Automate reconnaissant les mots finissant par ab

Un automate fini ou automate fini non déterministe (AFN) $\mathcal{A}$ sur un alphabet $A$ est un quadruplet $\mathcal{A} = (Q, \mathcal{F}, I, T)$ , où:

$Q$ est un ensemble fini d'états,
$\mathcal{F}\subset Q\times A\times Q$ est l'ensemble des transitions,
$I \subseteq Q$ est l'ensemble des état initiaux,
et $T \subseteq Q$ est un ensemble d'états finals ou terminaux.

Une transition $f = (p, a, q)$ est composée d'un état de départ $p$ , d'une étiquette $a$ et d'un état d'arrivée $q$ . Un calcul $c$ (on dit aussi un chemin ou une trace) est une suite de transitions consécutives:

$c=(p_0,a_1,p_1)(p_1,a_2,p_2)\cdots(p_{n-1},a_n,p_n)$

Son état de départ est $p 0$ , son étiquette est le mot $a_1a_2\cdots a_n$ et son état d'arrivée est $p n$ . Un calcul est réussi si son état de départ est un des états initiaux, et son état d'arrivée est un des états terminaux.

Un mot $w$ est reconnu ou accepté par l'automate s'il est l'étiquette d'un calcul réussi. Le langage reconnu par l'automate est l'ensemble des mots reconnus. Un langage est reconnaissable s'il est reconnu par un automate fini.

Le langage reconnu par un automate $\mathcal{A}$ est dénoté généralement par $L(\mathcal{A})$ .

Automate complet, automate émondé

Un automate est complet si pour tout état $q$ , et pour toute lettre $a$ , il existe au moins une transition partant de $q$ et portant l'étiquette $a$ .
Un état $q$ est accessible s'il existe un chemin d'un état initial à $q$ .
Un état $q$ est coaccessible s'il existe un chemin de $q$ à un état final.
Un automate est accessible (coaccessible) si tous ses états sont accessibles (coaccessibles).
Un automate est émondé si tous ses états sont à la fois accessibles et coacessibles.

Automate fini déterministe

Fig. 3 : Automate reconnaissant les mots commençant par

a b

Un automate fini déterministe (AFD) $\mathcal{A}$ sur un alphabet $A$ est un automate fini qui vérifie les deux conditions suivantes:

il possède un seul état initial;
pour tout état $q$ , et pour toute lettre $a$ , il existe au plus une transition partant de $q$ et portant l'étiquette $a$ .

Pour un automate déterministe, la fonction de transition $\delta : Q\times A \to Q$ est la fonction partielle définie par: $δ(q, a) = q'$ si $(q, a, q')$ est une transition. Si la fonction de transition est partout définie, l'automate est complet. La fonction de transition $δ$ est étendue en une application (partielle) $Q\times A^* \to Q$ en posant

$δ(q,ε) = q$ pour tout état $q$ . Ici $ε$ dénote le mot vide.
$δ(q, w a) = δ(δ(q, w), a)$ pour tout état $q$ , tout mot $w$ et toute lettre $a$ .

Il est d'usage de remplacer la notation $δ$ par un simple point. On écrit alors $q\cdot w$ à la place de $δ(q, w)$ , et la formule $δ(q, w a) = δ(δ(q, w), a)$ devient $q\cdot wa=q\cdot w\cdot a$ . Ceci montre aussi que la fonction de transition est une action du monoïde libre $A *$ sur l'ensemble $Q$ . On rencontre aussi la notation $\mathcal{A} = (Q, i, T)$ pour un automate déterministe, la fonction de transition étant sous-entendue (comme la loi de composition dans un groupe, par exemple). L'automate de la figure 3 est déterministe et incomplet. Son état initial est $1$ , et il possède un seul état final, l'état $3$ . Il reconnaît le langage $a b A *$ sur l'alphabet $A = {a, b}$ .

Extensions des automates finis

Il existe plusieurs généralisation des automates finis, selon la nature des étiquettes que l'on autorise sur les transitions: Un automate asynchrone est un automate où l'étiquette d'une transition peut être le mot vide. Un telle transition est appelée une $ε$ -transition. D'autres généralisations autorisent, comme étiquettes, des mots composés de plusieurs lettres. Enfin, la généralisation la plus large autorise comme étiquettes des langages rationnels, représentés par des expressions régulières. Toutes ces extensions n'augmentent pas la puissance des automates finis: un langage reconnu par une quelconque de ces extensions est reconnaissable par un automate fini, et même par un automate fini déterministe.

Déterminisation d'un automate fini

Il est toujours possible, à partir d'un automate fini $\mathcal{A}$ , de construire un automate fini déterministe $\mathcal{A'}$ reconnaissant le même langage.

Fig. 4 : Automate déterminisé des mots se terminant par

a b

Fig. 5 : Automate déterminisé et émondé

La méthode est appelée l'algorithme des parties (en) en français, et powerset construction en anglais.

Soit $\mathcal{A}= (Q, \mathcal{F}, I, T)$ un automate fini sur un alphabet $A$ .

On construit l'automate $\mathcal{A'}$ comme suit :

l'ensemble d'états de $\mathcal{A'}$ est l'ensemble $P = 2 Q$ des parties de l'ensemble $Q$ .
l'état initial de $\mathcal{A'}$ est $I$ .
les états terminaux de $\mathcal{A'}$ sont les parties $T'$ de $Q$ qui ont une intersection non vide avec $T$
la fonction de transition de $\mathcal{A'}$ est définie, pour $S\subseteq Q$ et $a\in A$ , par

$S\cdot a=\{s'\in Q\mid \exists s\in S: (s,a,s')\in \mathcal{F}$ .

L'automate $\mathcal{A'}$ est déterministe par construction.

Pour l'exemple de la figure 2, on obtient l'automate de la figure 4. Bien entendu, seuls les quatre états du haut sont utiles et même l'état $123$ peut être supprimé, puisqu'il n'est pas accessible. L'automate accessible déterminisé est celui de la figure 5.

Automates asynchrones

Fig. 6 : Automate asynchrone reconnaissant

a * b *

Fig. 7 : Automate synchronisé reconnaissant

a * b *

Un automate asynchrone est un automate fini autorisé à posséder des transitions étiquetées par le mot vide, appelées des $ε$ -transitions. L'automate de la figure 6 est asynchrone.

L'élimination des $ε$ -transitions se fait par un algorithme de fermeture transitive comme suit :

Pour chaque chemin d'un état $s$ à un état $t$ formé de $ε$ -transitions, et pour chaque transition de $t$ à un état $u$ portant une lettre $a$ , ajouter une transition de $s$ à $u$ d'étiquette $a$
Pour chaque chemin d'un état $s$ à un état $t$ terminal formé de

$ε$ -transitions, ajouter $s$ à l'ensemble des états terminaux.

Supprimer les $ε$ -transitions.

Dans l'exemple de la figure 6, on ajoute la transition $1\xrightarrow b 2$ dans la première étape, et on déclare que $1$ est état final dans la deuxième étape. On obtient l'automate de la figure 7.

Autres exemples d'automates finis

L'automate du début de l'article reconnaît les écritures binaire des entiers naturels multiples de 3. Par exemple, le nombre 28, dont l'écriture binaire est $10010$ , est reconnu: le calcul est

$s_0\xrightarrow1 s_1\xrightarrow0 s_2\xrightarrow0 s_1\xrightarrow1s_0\xrightarrow0 s_0$

On peut se convaincre qu'un entier $n$ mène, depuis l'état initial, à $s 0$ , $s 1$ ou $s 2$ , selon que le reste de sa divison par 3 est 0, 1, ou 2.

L'exemple suivant décrit un automate fini déterministe complet sur l'alphabet binaire $0,1$ , qui détermine si l'entrée contient un nombre pair de $0$ . Cet automate intervient dans la suite de Thue-Morse. L'automate est

$\mathcal{A} = (Q,p,\{p\})$ , avec $Q = {p, q}$ , et la fonction de transition donnée par:

$\begin{array}{c\|cc} &0&1\\\hline p&q&p\\ q&p&q \end{array}$

Chaque fois que l'on change d'état, la parité du nombre de $0$ change.

Langages rationnels et langages reconnaissables: le théorème de Kleene

Article détaillé : Théorème de Kleene.

Le mathématicien Stephen C. Kleene a démontré que les langages reconnus par les automates finis sont exactement les langages qui peuvent être décrits par les expressions rationnelles. De manière plus concise, il y a égalité entre la famille des langages rationnels et la famille des langages reconnaissables sur un alphabet fini donné.

De plus, la démarche est constructive: pour toute expression rationnelle, on peut construire un automate fini (déterministe ou non) qui reconnaisse cette expression ; de même, pour tout automate fini (déterministe ou non), on peut exprimer sous forme d'une expression rationnelle le langage qu'il reconnaît.

Expressions rationnelles et langages rationnels

Article détaillé : Expression rationnelle.

Les expressions rationnelles, ou expressions régulières sont des expressions qui décrivent les langages rationnels. Le terme expression régulière est antérieur, et les langages décrits par ces expressions sont naturellement aussi appelés langages réguliers.

Les expressions rationnelles, plus ou moins étendues, servent notamment à la recherche de motifs dans un texte.

Expressions rationnelles

Une expression rationnelle $E$ sur un alphabet $A$ est soit :

Un symbole dénotant le mot vide: $\epsilon$ ou $1$ ;
une lettre $a$ de l'alphabet $A$ ;
une union (ou somme) de deux expressions rationnelles $M$ et $N$ , notée $E = M | N$ ou $E = M + N$
une concaténation (ou un produit) de deux expressions rationnelles $M$ et $N$ , notée $E= M\cdot N$ ou simplement $E = M N$
une répétition d'une expression rationnelle $M$ notée $E = M *$ .

On distingue soigneusement l'expression rationnelle, qui est une simple expression, c'est-à-dire une chaîne de caractères qui représente un arbre d'expression, du langage que représente cette expression appelé le langage dénoté par l'expression. Ce langage est noté $L (E)$ et est défini récursivement, à partir de l'expression.

Construction d'automates finis à partir des expressions rationnelles

Il existe plusieurs méthodes pour construire un automate fini à partir d'une expression rationnelle :

la méthode de Thompson^[2].

Automate pour l'ensemble vide, le mot vide et une lettre

Automate pour l'union

Automate pour le produit

Automate pour l'étoile

Elle a été utilisée par Ken Thompson dans l'implémentation de la commande grep du système Unix.

Automate obtenu par la méthode de Thompson pour l'expression $(a+b)^*b(a+\epsilon)(a+b)^*$

On construit récursivement des automates pour les composants d'une expression. La forme particulière des automates permet de les combiner avec une grande facilité. L'automate obtenu est non déterministe asynchrone.

la méthode de Glushkov^[3]. Cette méthode, attribuée à l'informaticien Glushkov (en), permet de construire un automate non déterministe de même taille (nombre d'états) que la taille (nombre de symboles) de l'expression rationnelle.

Il a été observé que l'automate de Glushkov est le même que l'automate obtenu en supprimant les $ε$ -transitions de l'automate de Thompson.

la méthode des quotients ou résiduels, attribuée à Brzozowski (en)^[4]. On forme les quotients (ou résiduels) successifs de l'expression. Il n'y en a qu'un nombre fini de différents, après application d'un certain nombre de règles de simplification qui sont l'associativité, la commutativité et l'idempotence de l'opération $+$ .

Aucune de ces méthodes ne donne directement l'automate minimal d'un langage. Une méthode moins systématique consiste simplement à construire des automates pour la réunion, le produit et l'étoile de langages, et d'opérer récursivement :

Soit $\mathcal{A}(M)$ (respectivement $\mathcal{A}(N )$ ) l'automate fini reconnaissant le langage dénoté par l'expression rationnelle $M$ (respectivement $N$ ). Les constructions sont les suivantes:

Automate $\mathcal{A}(M|N)$ pour l'union :

Il suffit de faire l'union disjointe des automates $\mathcal{A}(M)$ et $\mathcal{A}(N)$ .

Automate $\mathcal{A}(M\cdot N)$ pour le produit :

L'automate a pour états les états de $\mathcal{A}(M)$ et de $\mathcal{A}(N)$ . Les états initiaux sont ceus de $\mathcal{A}(M)$ , les terminaux sont ceux de $\mathcal{A}(N)$ . Les transitions sont celles de $\mathcal{A}(M)$ et de $\mathcal{A}(N)$ , et de plus des $ε$ -transitions des états terminaux de $\mathcal{A}(M)$ vers les états initiaux de $\mathcal{A}(N)$

Automate $\mathcal{A}(M^*)$ pour l'étoile :

On part de l'automate $\mathcal{A}(M)$ que l'on augmente de deux états $i$ et $t$ . On ajoutes des $ε$ -transitions

i

à tout état initial de $\mathcal{A}(M)$

de tout état final de $\mathcal{A}(M)$ à

t

i

t

et de

t

i

L'état $i$ (resp. $t$ ) est l'état initial (resp. final) de $\mathcal{A}(M^*)$ .

Grammaires et langages rationnels

Les langages rationnels forment la classe la plus simple de la hiérarchie de Chomsky et sont, à ce titre, engendrés par des grammaires algébriques particulières, les grammaires linéaires droites ou grammaires linéaires gauches. Ce sont des grammaires où toutes les règles sont de la forme $X\to w$ ou $X\to wY$ , avec $w$ un mot ne contenant pas de variable et $X, Y$ des variables. (Pour les grammaires linéaire gauches, remplacer $X\to wY$ par $X\to Yw$ .)

On construit, pour une grammaire linéaire droite $G = (V, S, P)$ , un automate fini (généralisé, avec des mots comme étiquettes) comme suit : les états de l'automate sont les variables de la gframmaire, plus un état spécial $f$ . L'état initial est $S$ , le seul état final est $f$ . Chaque règle $X\to wY$ fournit une transition $(X, w, Y)$ de $X$ vers $Y$ d'étiquette $w$ , et chaque règle $X\to w$ fournit une transition $(X, w, f)$ de $X$ vers $f$ d'étiquette $w$ .

Minimisation d'un automate fini

Article détaillé: Minimisation DFA (en)

Deux automates finis sont équivalents s'ils reconnaissent le même langage. C'est un résultat remarquable de la théorie qu'il existe, pour tout automate fini, un seul automate fini déterministe minimal (c'est-à-dire ayant un nombre minimal d'état) qui est équivalent à l'automate donné. De plus, cet automate, appelé automate minimal se calcule efficacement par l'algorithme de Moore ou l'algorithme de Hopcroft (voir les livres cités en référence). L'unicité de l'automate ayant un nombre minimal d'état n'est plus vraie pour les automates non déterministes.

On peut ainsi décide de l'équivalence de deux automates en calculant, pour chacun, l'automate minimal correspondant, et en testant l'égalité des deux automates obtenus.

Monoïde de transition et monoïde syntaxique

Article détaillé : monoïde syntaxique.

Soit $\mathcal{A} = (Q, i, T)$ un automate fini déterministe complet sur un alphabet $A$ . Chaque mot $w$ définit une application $\sigma(w):Q\to Q$ donnée par

$q\sigma(w)=w\cdot q$

Ici l'argument de la fonction est noté à gauche de la fonction. On a

σ(x y) = σ(x)σ(y)

car en effet $q\sigma(xy)=q\cdot xy=q\cdot x\cdot y=(q\sigma(x))\cdot y= (q\sigma(x))\sigma(y)$ . L'application $\sigma:A^*\to Q^Q$ est donc un morphisme de $A *$ dans le monoïde des applications de $Q$ dans lui-mëme. L'image $σ(A *)$ est appelée le monoïde de transition de l'automate. Lorsque l'automate est minimal, le monoïde de transition est isomorphe au monoïde syntaxique du langage reconnu par l'automate.

Implémentation

Un automate fini peut être représenté en utilisant une table de transition d'état. On l'implémente alors sous forme logicielle avec une matrice de transition d'état. Dans certains cas, il est plus avantageux d'utiliser une matrice creuse, ou un énorme switch qui distribue selon les états, et pour chaque état un autre switchs qui distingue les symboles d'entrée.

L'implémentation d'automates finis se fait aussi, sous forme matérielle, par un dispositif de logique programmable appelé table logique programmable (en).

Notes

↑ Droste et al. 2009
↑ Thompson 1968. Elle est attribuée à McNaughton et Yamada dans Hopcroft et al. 2007
↑ Glushkov 1961
↑ Brzozowski 1964

Bibliographie

Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4)

Manfred Droste, Werner Kuich et Heiko Vogler, Handbook of Weighted Automata, Springer-Verlag, 2009 (ISBN 3642014917)

John E. Hopcroft, Rajeev Motwani, et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Prentice Hall, 2007 (ISBN 0321462254).
Troisième édition

Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003 (ISBN 978-2-7117-4807-5).
Traduction anglaise avec corrections: Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253)

Références

J. A. Brzozowski, « Derivatives of regular expressions », dans J. Assoc. Comput. Mach., vol. 11, 1964, p. 481–494

V. M. Glushkov, « The abstract theory of automata », dans Russian Math. Surveys, vol. 16, 1961, p. 1–53

Ken Thompson, « Regular expression search algorithm », dans Comm. Assoc. Comput. Mach., vol. 11, 1968, p. 419–422

Voir aussi

Sur les autres projets Wikimedia :

« Automate fini », sur Wikimedia Commons (ressources multimédia)
« Automate fini », sur le Wiktionnaire (dictionnaire universel)

Lien externe

L'histoire des automates finis a été décrite dans Les débuts de la théorie des automates par Dominique Perrin, paru dans Technique et science informatiques 1995, vol. 14, no4, pp. 409-433.

v · d · m

Informatique théorique

Théorie du calcul

Calculabilité	Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Ensemble récursivement énumérable
Modèle de calcul	Automate fini •Transducteur fini •Automate sur les mots infinis •Automate à pile •Automate linéairement borné • Automate cellulaire • Machine de Turing • Thèse de Church
Modes de calcul	Concurrence • Parallèlisme • Théorie de l'ordonnancement
Mesure et échelle de complexité	Réduction polynomiale • Problème NP-complet

Logique, syntaxe et sémantique

Logique mathématique	Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types
Grammaire formelle et systèmes de réécriture	Compilation • Expression rationnelle • Grammaire formelle • Transduction rationnelle • Langage rationnel • Langage algébrique • Langage contextuel • Théorie des langages
Sémantique	Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle
Spécifier, vérifier et concevoir des programmes	Interprétation abstraite • Méthodes formelles • Model checking

Algorithmique, complexité et mathématiques discrètes

Algorithmique	Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique
Problèmes et algorithmes numériques	Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité
Problèmes et algorithmes non-numériques	Algorithmes de la théorie des graphes • Arbre (structure de données) • Liste (informatique) • Table de hachage • Tas (informatique)
Théorie des graphes	Coloration de graphe • Problèmes de cheminement
Recherche opérationnelle	Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement
Données et codage	Combinatoire des mots •Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information

Portail de l'informatique théorique

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Automate fini de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

Automate Fini — Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
automate fini — baigtinis automatas statusas T sritis automatika atitikmenys: angl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. конечный автомат, m pranc. automate final, m; automate fini, m; automate terminal, m;… … Automatikos terminų žodynas
Automate fini déterministe — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate fini non déterministe — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate fini non déterministe généralisé — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate déterministe à états fini — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate Cellulaire — À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe !) de l application répétée de cette… … Wikipédia en Français
Automate a pile — Automate à pile Un automate à pile est une machine abstraite utilisée en informatique théorique et, plus précisément, en théorie des automates. Un automate à pile est semblable à un automate fini non déterministe mais il dispose également d une… … Wikipédia en Français
Automate À Pile — Un automate à pile est une machine abstraite utilisée en informatique théorique et, plus précisément, en théorie des automates. Un automate à pile est semblable à un automate fini non déterministe mais il dispose également d une pile qui peut… … Wikipédia en Français
Automate de Büchi — non déterministe reconnaissant les mots infinis contenant un nombre fini le a En informatique théorique, un automate de Büchi est un automate fini acceptant des mots infinis, avec une condition d acceptation particulière : une trace (ou… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Automate fini

Sommaire

Aperçu