Planche : 1


Automates

Très utilisés en informatique.


Planche : 2


Automate finis déterministes (DFA)

Un DFA est un quintuplet (Σ, Q, δ, q0, F) où


Planche : 3


Exemple simple de DFA

Idéalement, on exprime les automates par des dessins :

Ici Q = { 0,1,2,3,4 }, q0 = 0, F = { 3 }, et

δ =
q\cabc
014 
1222
    …

Planche : 4


Notation compacte

Transitions étiquetées par des ensembles de caractères.

La transition notée a-c compte pour trois.


Planche : 5


Exécution d'un DFA

Planche : 6


Exemple (utile ?) de DFA

Cet automate est un digicode cablé !

L'automate reconnaît un code à quatre chiffres, lequel ? 1234.


Planche : 7


Reconnaissance de la séquence 1211234

En cas de besoin, recharger la page pour relancer l'animation.


Planche : 8


Définition formelle de l'exécution

Si δ(q,c) = q', on note la transition effectuée :

q 
c
—→
 
 q'

Ainsi la lecture de abc par

s'écrit :

a
—→
 
c
—→
 
b
—→
 
3

C'est une reconnaissance parce que 0 est initial et 3 final.


Planche : 9


Consommation des mots

Soit un mot m=a0a1an−1 et une lecture

q0 
a0
—→
 
q1 
a1
—→
 
qn−1 
an−1
—→
 
 qn

On abrège en :

q0 
m
—→*
 
 qn

Un mot est reconnu par l'automate si et seulement si

q0 
m
—→*
 
 qn,   avec  qn ∈ F

Planche : 10


Langage reconnu (défini) par un DFA

Tout simplement l'ensemble des mots reconnus par le DFA.

m ∈ Σ ∣ q0 
m
—→*
 
 qq ∈ F }

Le langage reconnu par

est : { aab, abb, acb, bbb }.


Planche : 11


Implémentation possible des DFA

Une classe Auto.

class Auto {
  State init ;
  Set<Stateend ;
  … }

Classe des états :

class State {
  /* Identifiant unique (pratique) */
  int id ;
  /* Tableau des transitions, indexé par char (dans [0..256[) */
  State [] delta ;
  … }

Structure « creuse » pour les transitions ? Map<Character,State>.


Planche : 12


Implémentation de la reconnaissance

Méthode des objets Auto.

boolean isAccepted(String txt) {
  State q = init ;
  for (int k = 0 ; k < txt.length() ; k++) {
    char c = txt.charAt(k) ;
    if (q.delta[c] == nullreturn false ; // Bloqué
    q = q.delta[c] ;
  }
  return end.contains(q) ;
}

Planche : 13


Automates finis non-deterministes (NFA)

Un NFA est un quintuplet (Σ, Q, δ, q0, F) où

Changement : Fonction → Relation.

On peut avoir :

q 
c
—→
 
 q',   q 
c
—→
 
 q'',  et q' ≠ q''

Planche : 14


Exemple simple de NFA

Ou sont les ambiguïtés ?


Planche : 15


Reconnaissance par un NFA

La définition ne change pas.

m ∈ Σ ∣ q0 
m
—→*
 
 qq ∈ F }

Exemple, reconnaissance de abb.


Planche : 16


Mais alors, qu'est-ce qui change ?

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.


Planche : 17


Implémentation de la reconnaissance par NFA

Représentation de la relation δ : une fonction vers un ensemble.

class State {
  …
  Set<State> [] delta ;
  …
}

Essai et retour en arrière, veut dire tout essayer.

boolean isAccepted(String txt) {
  return run(txt, 0, init) ;
}

Planche : 18


Implémentation du backtracking

Récursivement bien sûr.

boolean run(String txtint kState q) {
  if (k >= txt.length()) {
    return end.contains(q) ;
  } else { 
    char c = txt.charAt(k) ;
    // Pour tous les états n tels que q —→c n.
    for (State n : q.delta[c]) {
      if (run(txtk+1, n))
        return true ; // Trouvé (chemin vers état final)
    }
    return false ; // Pas trouvé
  }
}

Planche : 19


Encore une sorte d'automate, le NFA-є

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.


Planche : 20


Exemple simple de NFA-є

On dessine les transitions spontanées sans aucune étiquette.


Planche : 21


Reconnaissance par un NFA-є

Exemple, reconnaissance de ab.

0 —→ 6 
a
—→
 
 7 —→ 8 —→ 5 
b
—→
 
 4

Planche : 22


Définitions formelles

Planche : 23


Algorithme de reconnaissance

Le backtracking fonctionne, mais est plus délicat que dans les NFA.

À cause des boucles de transitions spontanées.

0 —→ 1 —→ 2 —→ 0 —→ 1 —→ …

Planche : 24


Une nouvelle technique d'implémentation

Considérons des transitions entre ensembles d'états.

Les symboles —→c et —→* traduisent des fonctions entre ensembles d'états (notées c(Q) et є*(Q)).


Planche : 25


Lecture des mots avec les ensembles d'états

Définie comme :

Read
Q 
c
—→
 
 Q''
           
Q'' 
m
—→*
 
 Q'
Q 
cm
—→*
 
 Q'
Epsilon
Q —→* Q''
           
Q'' 
m
—→*
 
 Q'
Q 
m
—→*
 
 Q'
Init
Q 
є
—→*
 
 Q

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 —→*).


Planche : 26


Reconnaissance des mots avec ensembles d'états

Le mot m = a0a1an−1 est reconnu si et seulement si.

q0 } —→* Q1
a0
—→
 
 Q2 —→* Q3
a1
—→
 
 ⋯
an−1
—→
 
 Q2n —→* Q2n+1

Avec Q2n+1F ≠ ∅. 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
a1
—→
 
 q2 —→ ⋯ —→ q3
a1
—→
 
 ⋯
an−1
—→
 
 q2n —→ ⋯ —→ q2n+1

Avec q2n+1F


Planche : 27


Effectuer toutes les transitions à la fois

Exemple, reconnaissance de ab.

{0} —→* {0,1,4,5,6}
a
—→
 
 {2,7} —→* {2,4,5,7,8}
b
—→
 
 {3,4,5} —→* {2,3,4,5}

Planche : 28


Implémentation des transitions sur les ensembles

Planche : 29


Trois sortes d'automates, bilan provisoire

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-є.


Planche : 30


Rapport avec les expressions régulières

Étant donnée une expressions régulière p, on construit facilement un NFA-є qui reconnaît (définit) [[p]].


Planche : 31


Et inductivement

Soient p et q deux motifs, donc deux automates.

Nous avons compilé les motifs (haut-niveau) vers les automates (bas-niveau).


Planche : 32


Compilations alternatives

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)


Planche : 33


Optimiser mais rester correct

La règle « optimisée » de la concaténation est parfois fausse. Motifs a* et b*.

      

Faux (mot abab reconnu à tort) :

Correct :


Planche : 34


Compilations alternatives

De l'alternative

De la répétition.


Planche : 35


Exemple : le digicode 1234

Le motif est [0-9]*1234.

Plus vicieux, le digicode à deux codes.


Planche : 36


Tout est dans tout (et réciproquement)

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

Planche : 37


Principe de la déterminisation

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).


Planche : 38


Exemple facile de déterminisation

Soit :


Planche : 39


Plus raide, le digicode

Planche : 40


L'algorithme de Kleene

Planche : 41


Le mot de la fin

Ce document a été traduit de LATEX par HEVEA