Introduction à la théorie des automates
Automates - Qu'est-ce que c'est?
Le terme «automates» est dérivé du mot grec «αὐτόματα» qui signifie «auto-agissant». Un automate (Automata au pluriel) est un dispositif informatique autopropulsé abstrait qui suit automatiquement une séquence prédéterminée d'opérations.
Un automate avec un nombre fini d'états est appelé un Finite Automaton (FA) ou Finite State Machine (FSM).
Définition formelle d'un automate fini
Un automate peut être représenté par un 5-tuple (Q, ∑, δ, q 0 , F), où -
Q est un ensemble fini d'états.
∑ est un ensemble fini de symboles, appelé le alphabet de l'automate.
δ est la fonction de transition.
q0est l'état initial à partir duquel toute entrée est traitée (q 0 ∈ Q).
F est un ensemble d'états finaux de Q (F ⊆ Q).
Terminologies associées
Alphabet
Definition - Un alphabet est tout ensemble fini de symboles.
Example - ∑ = {a, b, c, d} est un alphabet set où 'a', 'b', 'c' et 'd' sont symbols.
Chaîne
Definition - Un string est une suite finie de symboles tirée de ∑.
Example - 'cabcad' est une chaîne valide sur l'ensemble d'alphabet ∑ = {a, b, c, d}
Longueur d'une chaîne
Definition- C'est le nombre de symboles présents dans une chaîne. (Désigné par|S|).
Examples -
Si S = 'cabcad', | S | = 6
Si | S | = 0, on l'appelle un empty string (Désigné par λ ou ε)
Kleene Star
Definition - L'étoile Kleene, ∑*, est un opérateur unaire sur un ensemble de symboles ou de chaînes, ∑, qui donne l'ensemble infini de toutes les chaînes possibles de toutes les longueurs possibles sur ∑ comprenant λ.
Representation- ∑ * = ∑ 0 ∪ ∑ 1 ∪ ∑ 2 ∪ ……. où ∑ p est l'ensemble de toutes les chaînes possibles de longueur p.
Example - Si ∑ = {a, b}, ∑ * = {λ, a, b, aa, ab, ba, bb, ……… ..}
Fermeture Kleene / Plus
Definition - L'ensemble ∑+ est l'ensemble infini de toutes les chaînes possibles de toutes les longueurs possibles sur ∑ à l'exclusion de λ.
Representation- ∑ + = ∑ 1 ∪ ∑ 2 ∪ ∑ 3 ∪ …….
∑ + = ∑ * - {λ}
Example- Si ∑ = {a, b}, ∑ + = {a, b, aa, ab, ba, bb, ……… ..}
Langue
Definition- Une langue est un sous-ensemble de ∑ * pour un alphabet ∑. Cela peut être fini ou infini.
Example - Si le langage prend toutes les chaînes possibles de longueur 2 sur ∑ = {a, b}, alors L = {ab, aa, ba, bb}