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

1 Langages formels
- 1.1 Alphabet
- 1.2 Mot
2 Définitions
3 Voir aussi

[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 = (a 1,..., a n)$ et $v = (b 1,..., b n)$ .

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$