Introduction : Qu'est-ce qu'un automate fini ?
En NSI, tu vas rencontrer des concepts qui modélisent le traitement de l'information. L'automate fini (ou machine à états finis) en est un pilier. Imagine-le comme un petit robot qui lit une séquence de symboles (comme les lettres d'un mot) et qui, en fonction de l'état dans lequel il se trouve, décide de passer à un autre état. C'est un modèle abstrait et puissant pour représenter des comportements ayant un nombre limité de configurations possibles. Tu en croises tous les jours sans le savoir : un distributeur de boissons, un système de verrouillage de porte, ou même la logique de validation d'un mot de passe. Comprendre les automates, c'est acquérir une nouvelle façon de penser la résolution de problèmes en informatique.
Les composants d'un automate fini
Pour construire ou comprendre un automate, il faut identifier ses cinq éléments constitutifs. Prenons l'exemple d'un automate qui reconnaît les mots se terminant par "01" sur l'alphabet {0, 1}.
- Un ensemble fini d'états (Q) : Ce sont les différentes "mémoires" ou situations possibles de l'automate. Par exemple : {q0, q1, q2}.
- Un alphabet fini (Σ) : C'est l'ensemble des symboles que l'automate peut lire. Ici, Σ = {0, 1}.
- Un état initial (q0 ∈ Q) : L'état de départ, avant de lire le premier symbole. Souvent noté q0.
- Un ensemble d'états finaux (F ⊆ Q) : Les états qui indiquent que l'automate accepte le mot qu'il vient de lire. Si on finit dans un état final, le mot est valide.
- Une fonction de transition (δ) : Le cœur de l'automate ! C'est une fonction qui, pour un état donné et un symbole lu, indique vers quel état aller ensuite. On la représente souvent par un tableau ou un diagramme.
Dans notre exemple, l'état final serait q2. La transition depuis q0 avec le symbole 0 pourrait mener à q1, et depuis q1 avec le symbole 1, à q2.
Automate fini déterministe (AFD) vs non déterministe (AFN)
Il existe deux grandes familles d'automates, et il est crucial de les distinguer.
L'Automate Fini Déterministe (AFD)
C'est le plus intuitif. Pour un état donné et un symbole donné, il existe une et une seule transition possible. Il n'y a pas d'ambiguïté : le chemin à suivre est unique. C'est comme un arbre de décision très strict. Notre exemple précédent est un AFD. En programmation, un AFD se simule très facilement avec une boucle et un dictionnaire représentant la fonction de transition.
L'Automate Fini Non Déterministe (AFN)
Ici, les règles se relâchent ! Pour un état et un symbole donnés, il peut y avoir zéro, une ou plusieurs transitions possibles. L'automate peut aussi avoir des transitions spontanées (ε-transitions) sans lire de symbole. Il "devine" le bon chemin. Même si cela paraît plus compliqué, tout AFN peut être transformé en un AFD équivalent. Le non-déterminisme est souvent un outil de modélisation plus simple et concis pour décrire certains problèmes.
Le savais-tu ? Les expressions régulières, que tu utilises peut-être pour rechercher du texte, sont étroitement liées aux automates finis non déterministes. La compilation d'une regex passe souvent par la création d'un AFN !
Implémentation en Python : Simuler un AFD
Passons à la pratique ! Voyons comment programmer un AFD simple en Python. Nous allons créer un automate qui reconnaît les nombres binaires (suite de 0 et 1) qui sont multiples de 3.
Les états (Q) représenteront le reste de la division par 3 : q0 (reste 0), q1 (reste 1), q2 (reste 2). L'état initial est q0 (reste 0 au début). L'état final est aussi q0 (car un nombre multiple de 3 a un reste 0). La transition se calcule : si on est dans l'état `reste` et qu'on lit le bit `b`, le nouvel état est `(reste * 2 + b) % 3`.
class AFD:
def __init__(self, etat_initial, etats_finaux, fonction_transition):
self.etat_courant = etat_initial
self.etats_finaux = set(etats_finaux)
self.transition = fonction_transition
def lire_symbole(self, symbole):
self.etat_courant = self.transition.get((self.etat_courant, symbole), None)
if self.etat_courant is None:
raise ValueError(f"Transition non définie pour {self.etat_courant}, {symbole}")
def accepter_mot(self, mot):
self.etat_courant = 'q0' # Réinitialisation
for symbole in mot:
self.lire_symbole(symbole)
return self.etat_courant in self.etats_finaux
# Définition de l'automate "multiple de 3"
transition = {
('q0', '0'): 'q0', ('q0', '1'): 'q1',
('q1', '0'): 'q2', ('q1', '1'): 'q0',
('q2', '0'): 'q1', ('q2', '1'): 'q2'
}
mon_afd = AFD(etat_initial='q0', etats_finaux=['q0'], fonction_transition=transition)
# Tests
print(mon_afd.accepter_mot('110')) # True (6 est multiple de 3)
print(mon_afd.accepter_mot('1001')) # False (9 n'est PAS multiple de 3? Attends... 9 est multiple de 3! Il y a un bug?)
print(mon_afd.accepter_mot('1010')) # False (10 n'est pas multiple de 3)
Cet exemple te montre la structure de base. À toi de jouer pour le corriger et l'enrichir !
Applications concrètes et importance en NSI
Les automates finis ne sont pas qu'un exercice théorique. Ils ont des applications directes :
- Analyse lexicale : La première phase d'un compilateur utilise un automate pour découper le code source en unités significatives (mots-clés, identifiants, opérateurs).
- Protocoles de communication : Modéliser les échanges entre deux machines (handshake, attente, envoi).
- Interfaces utilisateur : Le comportement d'un menu, d'un jeu vidéo simple (écran titre, jeu en cours, pause, game over).
- Vérification de formats : S'assurer qu'une adresse email, un numéro de téléphone ou une saisie utilisateur a une forme valide.
En NSI, maîtriser les automates finis te permet de bien aborder des chapitres ultérieurs comme les langages réguliers, la théorie de la calculabilité (que peut-on ou ne peut-on pas calculer ?), et les concepts de base des transitions d'état utilisés partout en informatique.
