Automates finis

 D´efinitions de base
D´efinition 1 Alphabet, chaˆıne
On appelle alphabet un ensemble fini de symbole. Une chaˆıne sur un alphabet est une s´equence ´eventuellement vide de symboles de . La s´equence vide est not´ee ǫ (epsilon). Les autres s´equences sont not´ees par la juxtaposition des symboles qui les composent.
D´efinition 2 Langage
Un langage est un ensemble de chaˆınes sur un alphabet .
D´efinition 3 Automate fini
Un automate fini est un quintuplet A = ( ,Q, δ, i, F) o`u :
– est un ensemble fini de symboles appel´e alphabet.
– Q est un ensemble fini dont les ´el´ements sont appel´es ´etats.
– δ est une relation de Q × × Q appel´ee transition ou ensemble des transitions de A.
– i est un ´etat de Q appel´e ´etat initial.
– F est un sous-ensemble de Q appel´e ensemble des ´etats finals de A.
L’ensemble des transitions δ est une relation, c’est-`a-dire un ensemble de triplets. Cet ensemble est n´ecessairement fini puisque Q et sont finis. Un automate fini est fait de composantes qui sont toutes finies ( , Q, δ, F), d’o`u le qualificatif de fini.
D´efinition 4 Repr´esentation graphique
Un automate fini peut ˆetre repr´esent´e graphiquement comme un graphe orient´e dont les sommets sont les ´etats et les arcs sont les transitions. Une transition (q1, x, q2) est repr´esent´ee par un arc reliant les sommets q1 et q2, ´etiquet´e par x.
Nous avons d´ej`a vu un exemple de repr´esentation graphique (figure 1). Reprenons pour cet exemple les diff´erentes d´efinitions. L’alphabet de l’automate est l’ensemble {e, j, n, o, s, t, u, z}.
Le quintuplet d´ecrivant l’automate est le suivant : ( ,∑ {0, 1, 2, 3, 4, 5, 6, 7, 8}, δ, 0, {4, 8}) avec
– ∑ = {e, j, n, o, s, t, u, z}