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}