Théorie des automates finis

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Sommaire

[modifier] Langages formels

[modifier] Alphabet

On appelle alphabet tout ensemble Σ fini, non vide. Les éléments de Σ sont appelés lettres.

[modifier] Mot

On appelle mot toute suite d'éléments de \Sigma ^{\N} à support fini, on pose ε la suite vide dit le mot vide. L'ensemble des mots sur Σ est noté Σ * .

L'opération fondamentale sur les mots est la concaténation, notée \cdot, elle est définie ainsi :

Soit deux mots u = (a1,...,an) et v = (b1,...,bn).

On a alors,

  • u \cdot \epsilon = \epsilon \cdot u =u
  • u \cdot v = (a_{1},...,a_{n},b_{1},...,b_{n})

La concaténation est associative : u \cdot{} (v \cdot w) = (u \cdot v) \cdot w

Par conséquent :

(\Sigma^{*}, \cdot) est un monoïde, c’est-à-dire que \cdot est associative et possède pour élément neutre \epsilon \in \Sigma^{*}.

[modifier] Définitions

[modifier] Automate fini

On appelle automate fini le quintuplet A = < Σ,Q,δ,I,F > , où :

  • Σ est un alphabet,
  • Q est un ensemble d'états stables,
  • I est une partie de Q appelée ensemble des états initiaux,
  • F est une partie de Q appelée ensemble des états finaux,
  • δ est une partie de Q \times \Sigma \times Q appelée ensemble des transitions. C'est une fonction de transition qui à un état du système et un élément de l'alphabet associe le passage à un autre état.

[modifier] Chemin

Un chemin est une suite de flèches consécutives. On note un chemin :

(q_0, a_1, q_1)\cdots(q_{k-1}, a_k, q_k), avec q_i \in Q, a_i \in \Sigma, (q_{i-1}, a_i, q_i) \in \delta.

On appelle trace ou étiquette la suite de lettres reconnue a_1\cdots a_k

On dit qu'un chemin est réussi lorsque q_0 \in I et q_k \in F

Un mot est reconnu lorsqu'il est l'étiquette d'un chemin réussi.

[modifier] Accessibilité

Un état, q\in Q, est dit :

  • accessible si et seulement s'il existe un chemin partant d'un état initial et allant jusqu'à q ;
  • coaccessible si et seulement s'il existe un chemin partant de l'état q et allant jusqu'à un état final.

Un automate est dit :

  • accessible si et seulement si tous ses états sont accessibles ;
  • coaccessible si et seulement si tous ses états sont coaccessibles ;
  • émondé s'il est accessible et coaccessible.

[modifier] Déterminisme

Un automate est déterministe si et seulement s'il possède un seul état initial et pour chaque état, il existe au plus une flèche sortante pour chaque lettre, c’est-à-dire si \forall q\in Q,\forall a\in \Sigma, |\delta(q,a)| \leq 1

[modifier] Voir aussi