DevLes automates finis sont un modèle fondamental de calcul. Avant toute étude, il faut maîtriser le vocabulaire de base. Ce glossaire couvre l'essentiel.
Alphabet, mot, langage
- Alphabet $\Sigma$ : ensemble fini non vide de symboles (ex. $\Sigma = \{a, b\}$, $\Sigma = \{0, 1\}$).
- Mot (ou chaîne) : suite finie de symboles de $\Sigma$. Le mot vide est noté $\varepsilon$.
- $\Sigma^*$ : ensemble de tous les mots sur $\Sigma$ (y compris $\varepsilon$). C'est le monoïde libre engendré par $\Sigma$.
- Langage : tout sous-ensemble $L \subseteq \Sigma^*$.
Automate fini déterministe (AFD)
Un AFD est un quintuplet $A = (Q, \Sigma, \delta, q_0, F)$ avec :
- $Q$ : ensemble fini d'états.
- $\Sigma$ : alphabet d'entrée.
- $\delta : Q \times \Sigma \to Q$ : fonction de transition (totale et déterministe).
- $q_0 \in Q$ : état initial.
- $F \subseteq Q$ : ensemble des états acceptants (ou finaux).
Automate fini non déterministe (AFN)
Un AFN remplace la fonction de transition par une relation : $\delta : Q \times \Sigma \to \mathcal{P}(Q)$. Depuis un état, il peut y avoir 0, 1 ou plusieurs transitions pour un même symbole.
Un AFN avec $\varepsilon$-transitions autorise aussi des transitions spontanées (sans consommer de symbole).
Théorème fondamental : tout AFN (avec ou sans $\varepsilon$-transitions) peut être converti en un AFD reconnaissant le même langage (construction par sous-ensembles).
Langage reconnu
Un mot $w$ est accepté par un automate si, partant de l'état initial et en lisant $w$ symbole par symbole, on atteint un état acceptant.
Le langage reconnu $L(A)$ est l'ensemble des mots acceptés. Un langage est dit rationnel (ou régulier) s'il est reconnu par un automate fini.
À retenir
Théorème de Kleene : un langage est rationnel si et seulement s'il est décrit par une expression rationnelle (regex). Les automates finis et les regex ont exactement le même pouvoir expressif.
Une question ou une suggestion ? Écrivez-nous.