Très utilisés en informatique.
Un DFA est un quintuplet (Σ, Q, δ, q0, F) où
Idéalement, on exprime les automates par des dessins :
Ici Q = { 0,1,2,3,4 }, q0 = 0, F = { 3 }, et
| δ = |
| ||||||||||||||||
Transitions étiquetées par des ensembles de caractères.
La transition notée a-c compte pour trois.
Cet automate est un digicode cablé !
L'automate reconnaît un code à quatre chiffres, lequel ? 1234.
En cas de besoin, recharger la page pour relancer l'animation.
Si δ(q,c) = q', on note la transition effectuée :
| q |
| q' |
Ainsi la lecture de abc par
s'écrit :
| 0 |
| 1 |
| 2 |
| 3 |
C'est une reconnaissance parce que 0 est initial et 3 final.
Soit un mot m=a0a1⋯an−1 et une lecture
| q0 |
| q1 |
| ⋯ qn−1 |
| qn |
On abrège en :
| q0 |
| qn |
Un mot est reconnu par l'automate si et seulement si
| q0 |
| qn, avec qn ∈ F |
Tout simplement l'ensemble des mots reconnus par le DFA.
| { m ∈ Σ⋆ ∣ q0 |
| q, q ∈ F } |
Le langage reconnu par
est : { aab, abb, acb, bbb }.
Une classe Auto.
Classe des états :
Structure « creuse » pour les transitions ?
Map<Character,State>.
Méthode des objets Auto.
Un NFA est un quintuplet (Σ, Q, δ, q0, F) où
Changement : Fonction → Relation.
On peut avoir :
| q |
| q', q |
| q'', et q' ≠ q'' |
Ou sont les ambiguïtés ?
La définition ne change pas.
| { m ∈ Σ⋆ ∣ q0 |
| q, q ∈ F } |
Exemple, reconnaissance de abb.
Il devient plus délicat, étant donnés un automate et un mot, de décider si l'automate reconnaît le mot.
On procède par essai et retour en arrière (backtrack).
Exemple, essayer de reconnaître abb.
Représentation de la relation δ : une fonction vers un ensemble.
Essai et retour en arrière, veut dire tout essayer.
Récursivement bien sûr.
Un automate fini non déterministe avec transitions spontanées (є-transitions) est un sextuplet (Σ, Q, δ, q0, F, є) où
Il y a des transitions spontanées. Si q et q' sont en relation par є, c'est-à-dire sans consommer de caractère, on note q —→ q'.
Attention Dans la littérature, on appelle souvent les NFA-є, NFA tout court.
On dessine les transitions spontanées sans aucune étiquette.
Exemple, reconnaissance de ab.
| 0 —→ 6 |
| 7 —→ 8 —→ 5 |
| 4 |
|
|
|
| { m ∈ Σ⋆ ∣ q0 |
| q, q ∈ F } |
Le backtracking fonctionne, mais est plus délicat que dans les NFA.
À cause des boucles de transitions spontanées.
| 0 —→ 1 —→ 2 —→ 0 —→ 1 —→ … |
Considérons des transitions entre ensembles d'états.
| Q' = { q' ∣ ∃ q ∈ Q, q |
| q'} |
| Q' = { q' ∣ ∃ q ∈ Q, q —→ ⋯ —→ q' } |
Les symboles —→c et —→* traduisent des fonctions entre ensembles d'états (notées c(Q) et є*(Q)).
Définie comme :
|
|
|
En outre, on peut se contenter d'alterner les étapes —→* et —→c, parce que
| Q —→* Q' —→* Q'' ⇒ Q' = Q'' = є*(Q) |
Donc, soient Q et m, Q' tel que Q —→*m Q' est uniquement déterminé (commencer et finir par une étape —→*).
Le mot m = a0a1⋯an−1 est reconnu si et seulement si.
| { q0 } —→* Q1 |
| Q2 —→* Q3 |
| ⋯ |
| Q2n —→* Q2n+1 |
Avec Q2n+1 ∩ F ≠ ∅. C'est-a-dire
| є*(an−1(⋯ a1(є*(a0(є*({q0}))))⋯)) ⋂ F ≠ ∅ |
Correct, car équivalent par définition des transitions sur les ensembles à l'existence de :
| q0 —→ ⋯ —→ q1 |
| q2 —→ ⋯ —→ q3 |
| ⋯ |
| q2n —→ ⋯ —→ q2n+1 |
Avec q2n+1 ∈ F
Exemple, reconnaissance de ab.
| {0} —→* {0,1,4,5,6} |
| {2,7} —→* {2,4,5,7,8} |
| {3,4,5} —→* {2,3,4,5} |
|
|
Pour ce qui est de la classe des langages définis :
| L(DFA) ⊆ L(NFA) ⊆ L(NFA-є) |
Évident, car les DFA sont des cas particuliers de NFA qui sont des cas particuliers de NFA-є.
Étant donnée une expressions régulière p, on construit facilement un NFA-є qui reconnaît (définit) [[p]].
Soient p et q deux motifs, donc deux automates.
Nous avons compilé les motifs (haut-niveau) vers les automates (bas-niveau).
Soit p = abc, si on suit la règle, on a :
Alors que l'automate suivant est plus simple et convient.
Cela revient à modifier la règle de la concaténation (confondre l'état final de p et l'état initial de q)
La règle « optimisée » de la concaténation est parfois fausse. Motifs a* et b*.
 |  |
Faux (mot abab reconnu à tort) :
Correct :
De l'alternative
De la répétition.
Le motif est [0-9]*1234.
Plus vicieux, le digicode à deux codes.
Théorème (Rabin-Scott) Étant donné un NFA-є il existe un DFA qui reconnaît exactement le même langage.
Corollaire : L(NFA-є) ⊆ L(DFA)
Conséquence :
| L(DFA) = L(NFA) = L(NFA-є) |
Théorème (Kleene) Étant donné un DFA, il existe une expression régulière p telle que le langage par lui reconnu est exactement [[p]].
Conséquence :
| L(DFA) = L(NFA) = L(NFA-є) = langages réguliers |
Soit (Σ, Q, δ, q0, F, є) un NFA-є. Le DFA équivalent est :
L'algoritme de déterminisation est assez malin, mais il peut être exponentiel (le DFA peut avoir 2|Q| états).
L'algorithme est important en pratique (implémentation efficace des expressions régulières).
Soit :
Ce document a été traduit de LATEX par HEVEA