Automate déterministe à états fini

Automate déterministe à états fini

Automate fini

Page d'aide sur l'homonymie Pour les articles homonymes, voir Automate.
Exemple d'un diagramme d'automate fini.

Un automate fini (on dit parfois machine à états finie), en anglais finite state automaton ou finite state machine (FSA, FSM), est une machine abstraite utilisée en théorie de la calculabilité et dans l'étude des langages formels. C'est un outil fondamental en Informatique, où il intervient notamment en compilation des langages informatiques (procédé permettant de passer d'un langage de haut niveau en langage machine binaire).

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. L'automate est dit « fini » car il possède un nombre fini d'états distincts : il ne dispose donc que d'une mémoire bornée.

Un automate fini forme un graphe orienté étiqueté, dont les états sont les sommets et les transitions les arêtes étiquetées.

Sommaire

Utilisation

Il existe plusieurs types de machines à états finie. Les « accepteurs » produisent en sortie une réponse « oui » ou « non », c'est-à-dire qu'ils acceptent (oui) ou rejettent (non) l'entrée. Les systèmes de reconnaissance classent l'entrée par catégorie. Enfin, les capteurs sont employés pour produire un certain résultat en fonction de l'entrée.

Les automates finis peuvent caractériser des langages (c'est-à-dire, des ensembles de mots) finis (le cas standard), des langages de mots infinis (automates de Rabin, automates de Büchi), ou encore divers types d'arbres (automates d'arbres).

Une autre distinction est faite entre les automates déterministes et les non déterministes (qu'il conviendrait mieux de qualifier de « nondéterministes »). Un automate est déterministe si, pour chacun de ses états, il y a au plus une transition pour chaque étiquette possible. S'il y en a exactement une, on parle alors d'automate déterministe complet. Dans les automates non déterministes, il peut y avoir un nombre quelconque de transitions à partir d'un état donné pour une étiquette donnée. Ici, le terme « non déterministe » n'est pas la négation de « déterministe ».

Un automate fini non déterministe est toujours transformable en un automate fini déterministe équivalent. Dans le pire des cas, l'automate déterministe produit est exponentiellement plus grand (en nombre d'états) que l'automate non déterministe, mais il est en général possible d'en diminuer considérablement le nombre d'états.

Indépendamment de la théorie, les machines à états finis se rencontrent également dans les circuits digitaux, où l'entrée, l'état et le résultat sont des vecteurs de bits de taille fixe (machines de Moore et machines de Mealy). 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.

Définitions formelles

Automate fini déterministe

Un automate fini déterministe (AFD) A est un quintuplet A = (E,Σ,t,i,Q) où :

  • E est un ensemble fini d'états,
  • Σ est un alphabet, c'est-à-dire un ensemble de lettres,
  • t : E \times \Sigma \rightarrow E est une fonction de transition,
  • i \in E est l'état de départ ou état initial,
  • et Q \subseteq E est un ensemble d'états « accepteurs » ou états terminaux.

L'automate prend un mot (constitué de symboles de son alphabet) en entrée et démarre dans son état initial. Il parcourt ensuite le mot en utilisant la fonction de transition t afin de déterminer, pour chaque lettre, le prochain état à parcourir en utilisant l'état courant et le symbole venant d'être lu.

Si, à la fin de la lecture, la machine est dans un état accepteur, on dit qu'elle accepte l'entrée. Autrement, on dit qu'elle la rejette.

L'ensemble des entrées acceptées forme un langage L, qui est le langage « reconnu » par l'automate A. On dit que « A reconnaît le langage L ». Autrement dit, A reconnaît tous les mots de L, et A refuse tous les mots de Σ* (* désigne l'étoile de Kleene) qui ne sont pas dans L.

Un automate de Büchi déterministe opère sur des mots infinis. Un mot infini est accepté si l'automate de Büchi passe un nombre infini de fois par les états acceptants lorsqu'il lit ce mot.

Automate fini non déterministe

Un automate fini non déterministe (AFN) A est un quintuplet A = (E,Σ,t,I,Q) où :

  • E est un ensemble fini d'états,
  • Σ est un alphabet,
  • T : E \times (\Sigma \cup \{\varepsilon\}) \rightarrow \mathcal{P}(E) est une fonction de transition,
  • I \subseteq E est un ensemble non vide d'états initiaux,
  • et Q \subseteq E est un ensemble d'états terminaux.

\mathcal{P}(E) est l'ensemble des parties de E (aussi noté 2E) et \varepsilon est la séquence de taille nulle, aussi appelée « mot vide ».

La machine A démarre dans l'état de départ et reçoit en entrée une séquence w de symboles de son alphabet. Elle emploie la relation de transition T pour déterminer le ou les prochains états atteignables en utilisant les états actuellement atteignables et le symbole venant d'être lu. On dit que l'automate non déterministe A accepte l'entrée w si un des états accepteurs est atteignable au terme de la lecture de l'entrée, c'est-à-dire s'il existe au moins un parcours des états de l'automate tel qu'à la fin la tête de lecture arrive sur un état terminal. Sinon, A rejette w.

L'ensemble des entrées acceptées forme un langage dénoté généralement par L(A).

Automate fini non déterministe généralisé

Un automate fini non déterministe généralisé (AFNG) A est un quintuplet (E,Σ,t,I,q) où :

  • E est un ensemble d'états,
  • Σ est un alphabet,
  • t : (E \setminus \{q\}) \times (E \setminus \{i\}) \rightarrow R est une fonction de transition,
  • i \in E est l'état initial,
  • et q \in E est l'état accepteur.

R est l'ensemble de toutes les expressions rationnelles sur l'alphabet Σ.

Un AFD ou un AFN peut facilement être converti en AFNG et alors l'AFNG peut être facilement converti en expression rationnelle en réduisant le nombre d'états jusque à ce que E = {s,a}.

Exemples de machines à états finis

machine à états finie déterministe

L'exemple suivant décrit une machine à états finie déterministe sur un alphabet binaire, qui détermine si l'entrée contient un nombre pair de 0.

A = (E,Σ,t,i,Q)

  • E = {E1,E2}
  • Σ = {0,1}
  • i = E1
  • Q = {E1}
  • La fonction de transition t est définie comme suit :
    • t(E1,0) = E2
    • t(E1,1) = E1
    • t(E2,0) = E1
    • t(E2,1) = E2

Si lors du parcours d'une entrée, on se trouve à l'état E1, cela signifie qu'il y a eu un nombre pair de 0 dans l'entrée jusqu'à présent, si on se trouve à l'état E2, cela signifie qu'il y en a eu un nombre impair. Un 1 dans l'entrée ne change pas l'état de l'automate. Quand l'entrée finit, l'état montrera si l'entrée a contenu un nombre pair de 0 ou pas.

Langages rationnels et langages reconnaissables

Stephen 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. En d'autres termes, 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.

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

Optimisation et mise sous forme canonique

Optimiser ou minimiser un automate fini, c'est-à-dire calculer l'automate avec le plus petit nombre d'états et qui reconnait le même langage, est un problème décidable, à la différence de problèmes similaires pour des machines informatiques plus puissantes. En outre, il est possible de construire une version canonique de n'importe quel automate fini, afin de déterminer l'égalité de deux automates.

Ces deux problèmes peuvent être résolus en utilisant un algorithme de coloriage.

Puissance informatique

Les machines à états finis peuvent uniquement identifier des langages rationnels, et par conséquent elles sont moins puissantes que les machines de Turing. Il existe des problèmes que l'on peut décider mais qui ne sont pas calculables en utilisant une machine à états finie.

Pour chaque machine non déterministe ayant n états, une machine déterministe de puissance égale peut être construite avec un algorithme. Cette machine déterministe a dans le pire des cas un nombre d'états égal au nombre de parties de l'ensemble des états de la machine initiale, c’est-à-dire 2n.

Représentation

Une machine à états finie peut être représentée en utilisant une table de transition d'état ou un diagramme d'état.

Exécution

Une machine à états finie peut être implémentée sous forme logicielle avec une matrice de transition d'état.

Dans certains cas, il est plus avantageux d'utiliser une matrice creuse implémentée avec des listes liées ou un énorme switch pour détecter l'état interne et puis les différents switchs plus petits pour décoder le symbole d'entrée.

Une machine à états finie peut aussi être implémentée sous forme matérielle avec un dispositif de logique programmable.

Enfin, une manière plus élégante et plus souple est d'implémenter le patron de conception state si le langage s'y prête.

Voir aussi

Articles connexes

Références

  • (fr) Jacques Sakarovitch, Eléments de théorie des automates, Vuibert 2003. (ISBN 978-2-7117-4807-5).
  • (fr) Olivier Carton, Langages formels, calculabilité et complexité. Vuibert 2008, (ISBN 978-2-7117-2077-4).

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Automate fini ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Automate déterministe à états 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 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 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ér …   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 une généralisation des automates finis: il dispose en plus d une mémoire infinie organisée en… …   Wikipédia en Français

  • Automate sur les mots infinis — En informatique théorique, et spécialement en théorie des automates un automate sur les mots infinis ou ω automate est un automate fini, déterministe ou non, qui accepte des mots infins. Comme un tel automate ne s arrête pas, les conditions d… …   Wikipédia en Français

  • Automate D'arbres — Sommaire 1 Introduction 2 Définitions 3 Propriétés 3.1 Déterminisme 3.2 Reco …   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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”