- est un alphabet,
- est un ensemble fini, appelé ensemble d’états,
- est une fonction (partielle) de dans appelée fonction de transitions,
- est un élément de appelé état initial,
- est une partie de appelée ensemble des états finaux.
Un automate fini déterministe (AFD) est un modèle mathématique qui reconnaît un langage régulier, qui est un ensemble de chaînes de caractères composées de symboles d’un alphabet fini. Un DFA est un type de machine à états finis qui possède un ensemble fini d’états, un ensemble fini de symboles d’entrée, une fonction de transition qui fait correspondre un état et un symbole d’entrée à un état suivant, un état de départ et un ensemble d’états d’acceptation ou d’états finaux. L’idée de base d’un DFA est de commencer dans l’état de départ, de lire un symbole d’entrée, de passer à l’état suivant selon la fonction de transition, et de répéter l’opération jusqu’à la fin de l’entrée. Si l’état final atteint est un état d’acceptation, l’entrée est acceptée ; sinon, l’entrée est rejetée.
Pour prouver qu’un langage est rationnel, nous devons montrer qu’il peut être reconnu par un AFD ou un modèle équivalent, tel qu’un automate fini non déterministe (AFN), une expression régulière ou une grammaire régulière. Cela signifie que chaque chaîne du langage peut être générée ou acceptée par une séquence finie d’étapes qui n’impliquent que des opérations simples sur les symboles, telles que la concaténation, l’union, la fermeture de Kleene ou la substitution. Par exemple, le langage de toutes les chaînes binaires qui ont un nombre pair de zéros peut être reconnu par le DFA suivant :
Ce DFA a deux états, q0 et q1, qui représentent la parité du nombre de zéros vus jusqu’à présent. Si le symbole d’entrée est un zéro, le DFA passe à l’autre état ; sinon, il reste dans le même état. Si l’état final est q0, la chaîne d’entrée est acceptée comme ayant un nombre pair de zéros ; sinon, elle est rejetée comme ayant un nombre impair de zéros.
Un automate peut être défini comme une machine qui fonctionne sur des entrées selon un ensemble fixe de règles ou d’instructions, sans intervention externe ni retour d’information. Un automate peut être déterministe ou non déterministe, selon qu’il a un état suivant unique pour chaque symbole d’entrée ou qu’il peut avoir plusieurs états suivants possibles. Un automate peut être utilisé pour résoudre divers problèmes, tels que la reconnaissance de modèles, l’analyse syntaxique de langages, la simulation de systèmes ou la vérification de propriétés. Un automate peut également être considéré comme un dispositif informatique qui transforme les entrées en sorties, sur la base d’un algorithme ou d’un programme donné.
Le langage reconnu par un DFA est l’ensemble de toutes les chaînes de caractères qui peuvent être acceptées par le DFA, en commençant par l’état de départ et en terminant par un état d’acceptation. Le langage reconnu par un DFA est toujours un langage régulier, ce qui signifie qu’il peut être généré par une expression régulière, une grammaire régulière ou un autre DFA. Le langage reconnu par un DFA peut être exprimé comme L(D) = {w | δ(q0, w) ∈ F}, où δ(q, w) est l’état atteint par le DFA lors de la lecture de l’entrée w à partir de l’état q, et ∈ représente l’appartenance à l’ensemble des états d’acceptation F.
Les deux principales sources d’énergie pour les automates sont le flux d’entrée et les états internes. Le flux d’entrée fournit les symboles d’entrée qui déclenchent les transitions entre les états, tandis que les états internes stockent la configuration actuelle de l’automate, qui détermine son comportement. L’énergie consommée par un automate dépend du nombre et de la complexité des opérations effectuées sur le flux d’entrée et les états internes. En général, un DFA nécessite moins d’énergie qu’un NFA ou qu’une machine de Turing, car il a moins d’états et moins de flexibilité.
Le principal problème du modèle des automates finis est qu’il ne permet pas de reconnaître les langages non réguliers, c’est-à-dire les langages qui ne peuvent être générés ou reconnus par aucune machine à états finis. Les langages non réguliers comprennent de nombreux exemples importants, tels que les langages sans contexte, les langages sensibles au contexte et les langages récursivement énumérables. Pour traiter les langages non réguliers, des modèles de calcul plus puissants sont nécessaires, tels que les automates pushdown, les automates à limites linéaires ou les machines de Turing. Ces modèles peuvent gérer des structures et des processus plus complexes, mais au prix d’une complexité et d’une consommation de ressources accrues.