Automates finis déterministes (AFD)

{\star} Soit {\Sigma} un alphabet, et soit {\Sigma} l’ensemble des mots sur cet alphabet. {\star} Un automate fini déterministe est la représentation abstraite d’une machine capable de reconnaître si un mot de {\Sigma} appartient (ou n’appartient pas ) à un certain langage rationnel L.

  • on verra que pour tout langage rationnel L, il y a un automate fini déterministe reconnaissant les seuls mots de L.
  • inversement, on verra que les mots reconnaissables par un automate fini déterministe constituent un langage rationnel.

Il faut imaginer un automate fini déterministe (en abrégé AFD) comme une machine possédant un nombre fini d’états possibles, démarrant dans un état initial unique, capable de lire une à une les lettres du mot qui lui est proposé, et dont l’état évolue à chaque lettre lue avant (on l’espère) d’aboutir dans un état d’acceptation (de reconnaissance ) du mot.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :