Les automates finis

Un automate fini est composé par :

Identifiant	Description	Symbole graphique
I	Un état initial, I ∈ S.
F	Un ensemble d'état final, F ⊆ S.
	Note : Symbole graphique d'un état initial et final.
A	Un alphabet composé de symbole: caractère, ensemble de caractère (négatif ou non).
S	Un ensemble d'état.
T	Un ensemble de transitions. (s1,a)→s2 est une transition avec s1,s2 ∈ S et a ∈ A.

	Transition à un caractère La machine passe d'un état à un autre en lisant un caractère.
	Transition pour un ensemble de caractère Si le caractère lu fait partie de l'ensemble de caractère accepté, la machine change d'état. L'automate perd en performance avec mais cette perte reste négligeable en utilisant des caches mémoires. Ce type de transition est nécessaire pour les ensembles de caractères négatifs. Elles permettent aussi de compresser l'automate.
	Transition ε (epsilon) La machine passe d'un état à un autre sans lire de caractère. Ce type de transition est utilisé dans les AFN.

Transition à un caractère

La machine passe d'un état à un autre en lisant un caractère.

Transition pour un ensemble de caractère

Si le caractère lu fait partie de l'ensemble de caractère accepté, la machine change d'état.

L'automate perd en performance avec mais cette perte reste négligeable en utilisant des caches mémoires.
Ce type de transition est nécessaire pour les ensembles de caractères négatifs.
Elles permettent aussi de compresser l'automate.

Transition ε (epsilon)

La machine passe d'un état à un autre sans lire de caractère.
Ce type de transition est utilisé dans les AFN.