Des NFA-є aux NFA


L'énoncé en Pdf.

Projet à rendre par courier électronique (Luc.Maranget@inria.fr) avant le mercredi 14 février, minuit.

1  Preliminaires

Le projet est une extension du dernier TP sur les automates. Sont fournies deux classes State et Auto qui sont une solution au TP.

Par rapport à celle du TP, notre classe State présente une grosse et une petite différence.

2  Fabriquer un NFA sans transitions spontanées

Ici nous utilisons largement les concepts et les notations du cours 09.

En théorie

Soit A un NFA-є, A = (Q, δ, q0, F, є). Nous définissons d'abord les états significatifs. Sont significatifs :

Nous definissons ensuite un NFA équivalent au NFA-є, B = (Q', δ', q0', F')

Un algorithme

Les structures de données des classes State et Auto interdisent le partage des états entre les automates A et B — essentiellement parce que les transitions sont des champs des états State. Il va donc falloir procéder à une copie des états significatifs de A.

  1. Créer une table d'associations M, des états de A vers les états de B. Poser Q' = ∅, F' = ∅.
  2. Pour chaque état significatif o de A :
    1. Créer un nouvel état n et ajuster Q' ← Q' ∪ { n }.
    2. Ajouter l'association on à M, en outre :
      1. Si o est q0, alors q'0 est n.
      2. Si єA*(o) ∩ F ≠ ∅, alors F' ← F' ∪ { n }.
    À ce stade, tous les états de Q' sont connus, il reste à calculer les transitions δ'.
  3. Pour chaque état significatif o de A :
    1. Retrouver n = M(o).
    2. Calculer O1 = єA(o), pour chaque o1 dans O1.
      1. Pour chaque transition (dans A)
        o1 
        c
        —→
         
         o2,
        1. Calculer O3 = єA(o2).
        2. Pour chaque o3 de O3, ajouter la transition suivante à B.
          n 
          c
          —→
           
           M(o3).
    Avec les notations du cours, on vient de calculer cB(n) = єA*(cAA*(o))).

Un peu d'aide

Pour implémenter l'algorithme il est bon de savoir que…

Pour vous donner une idée plus précise des techniques employées, la classe Auto fournie, comporte une méthode de copie des automates.

  // Exemple utile : copie de l'automate this.
  Auto copy() {
    // Le résultat
    Auto r = new Auto () ;
    // Association des anciens états (de this) vers les nouveaux (de r)
    Map<StateStateold2new  = new TreeMap<State,State> () ;

    /* Fabriquer les états de la copie */
    for (State o : states) {
      State n = null ;
      if (o == initial) { // Dans ce cas, le nouvel état existe déjà
        n = r.initial ;
      } else { // Ici il  faut le créer
        n = new State () ;
        r.states.add(n) ;
      }
      old2new.put(on) ; // Enregistrer que n est la copie de o
      // o final <=> n final
      if (accept.contains(o)) r.accept.add(n) ;
    }

    /* Fabriquer les transitions de la copie */
    for (State o : states) {
      State n = old2new.get(o) ; // Récupérer la copie de l'état o
      // Copier les transitions spontanées
      for (State oo : o.doTransitions()) {
        n.addTransition(old2new.get(oo)) ;
      }
      // Copier les transitions étiquetées
      for (Map.Entry<Character,Set<State>> e :
             o.getAllTransitions().entrySet()) {
        char c = e.getKey() ;
        for (State oo : e.getValue()) {
          n.addTransition(cold2new.get(oo)) ;
        }
      }
    }
    return r ;
  }

Noter que vous n'avez normalement pas besoin d'appeler copy, c'est juste un exemple.

3  Ce qu'il faut faire

Enrichir la classe Auto de deux méthodes.

Pour tester votre code, vous disposez des moyens suivants.


Ce document a été traduit de LATEX par HEVEA