0. Aidez nous à améliorer ce cours...

...en répondant rapidement à ce sondage.

1. Automates finis non-déterministes à epsilon transitions

Le but de cet exercice est d'apprendre à manipuler les automates. Les automates sont principalement utilisés pour l'analyse lexicale, et servent à représenter/implementer les expression régulières. Nous allons écrire deux classes au cours de ce TD : State et Automaton.

Les états sont codés par la classe State. L'état poubelle est représenté par l'objet null.
Un état contient l'ensemble des états vers lequel mène une epsilon transition.
En plus un état contient la table de transition. C'est une table dont les indices sont les 256 codes ASCII (étendu) des caractères, et les entrées les états destinations.
Les ensembles d'états sont codés par un arbre AVL.
La classe Automaton réalise un automate fini non-déterministe à epsilon transitions. Elle contient l'ensemble de ses états, l'état initial et l'ensemble des états finaux.

Remarque 1.1 - TreeSet<State>

On va représenter les ensembles d'états par des arbres AVL. Mais ne craignez rien, on ne va pas passer de nouveau deux heures à écrire une classe ArbreAVL comme en décembre. On va simplement utiliser une classe toute faite, TreeSet<State>. Il s'agit d'une classe générique et on précise entre chevrons la classe des objets stockés dans les sommets de l'arbre. La classe TreeSet réalise un ensemble d'objets par des arbres AVL.
Pour pouvoir l'utiliser il faut ajouter import java.util.*; au fichier .java. Nous auront besoin des méthodes suivantes

a.add(s) permet d'ajouter un état s à l'ensemble a.
a.addAll(b) permet de remplacer l'ensemble a par l'union avec un autre ensemble b donné.
a.contains(s) permet de tester si l'état s est un élément de l'ensembe a.
a.isEmpty() permet de tester si a est vide.
for (State s: a) permet d'itérer sur tous les états s de l'ensemble a.

Question 1.2 - State

Pour que la classe TreeSet sache comparer les états il faut une méthode compareTo à la classe State. L'appel à s.compareTo(t) doit retourner un entier <0, l'entier 0 ou un entier >0 suivant que

s<t,
s=t

ou s>t. On va tout simplement utiliser l'ordre sur les identifiant et donc retourner id-t.id.

Pour que la classe TreeSet sache que State est munie d'une méthode compareTo, il faut déclarer que State implémente l'interface Comparable<State>.

Écrivez maintenant la classe State qui représente les états. Munissez la des attributs/méthodes suivants : (pensez à importer java.util.* pour TreeSet)

int id; // identificateur unique de l'état
State() // le constructeur pose id. Savez-vous comment attribuer succéssivement 0,1,2,.. à chaque nouvelle création ?
public int compareTo(State t) //comparer cet objet avec t
State transition[]; // la table de transition
void addTransition(char c, State next) // ajoute une transition pour la lettre c
TreeSet<State> epsilon; // l'ensemble des états cibles des transitions epsilon
void addTransition(State next) // ajoute une epsilon transition
static void epsilon_closure(TreeSet<State> set) // ajoute à l'ensemble set tous les états atteignables par des epsilon-transitions.

Pour la méthode epsilon_closure notez qu'on ne peut pas modifier en Java l'ensemble qu'on est en train de parcourir. Une solution serait alors de produire en une itération intérieure l'ensemble des états à ajouter à set. Puis l'itération extérieure prendra fin quand cet ensemble sera enfin vide.
Testez en avec cette méthode.

     public static void main(String []args) {
        State []tab  = {new State(), new State(), new State(), new State()};
        tab[2].addTransition('x', tab[3]);
        tab[2].addTransition(tab[0]);
        tab[1].addTransition(tab[2]);
        tab[0].addTransition(tab[1]);
        for (State s: tab) {
            for (State n: s.epsilon) 
                System.out.println(""+s.id+"->"+n.id);
            for (char c=0; c<256; c++)
                if (s.transition[c]!=null)
                    System.out.println(""+s.id+"-"+c+"->"+s.transition[c].id);
        }

        TreeSet<State> set = new TreeSet<State>();
        set.add(tab[1]);
        State.epsilon_closure(set);
        System.out.print("cloture(1) =");
        for (State s: set)
           System.out.print(" "+s.id);
        System.out.println(); 
    }

Vous devriez avoir l'affichage suivant.

0->1
1->2
2->0
2-x->3
cloture(1) = 0 1 2

Question 2 - Automaton

Ecrivez la classe Automaton avec les attributs, méthodes suivants : (La méthode dump a besoin qu'on importe java.io.*. )

TreeSet<State> states; // l'ensemble des états de l'automate
State initial; // l'état initial
TreeSet<State> accept; // l'ensemble des états acceptants
Automaton() // crée un automate qui ne reconnait rien du tout
Automaton(TreeSet<State> _states, State _initial, TreeSet<State> _accept)
// crée un automate avec les valeurs données
static Automaton new_WORD(String word) // cr'ee un automate qui reconnait un mot donné et rien d'autre

Ajoutez la méthode d'affichage suivante, qui écrit l'automate dans un fichier dont le nom sera tmp??.dot où ?? est l'entier qui est passé en paramètre à dump.

     /** affiche l'automate comme un graphe en notation DOT
        ... enfin retourne une chaine qui correspond a l'affichage plutot
    */
    public void dump(String word, int i, Set<State> marked) {
        try {
            PrintWriter out = new PrintWriter(String.format("tmp%02d.dot",i));
            String label="";
            if (word!=null) {
                label=" label=\"";
                for (int j=0; j<=word.length(); j++) {
                    if (j==i)
                        label+='>';
                    else
                        label+=' ';
                    if (j<word.length())
                        label+=word.charAt(j);
                }
                label += "\";\n";
            }
            
            // imprimer tout ce qui est sp'ecifique au graphe
            out.println("digraph {\n"+
                        " rankdir=LR;\n"+
                        label+
                        " init [shape=point];\n"+
                        " init->"+initial.id+";\n"      );
            
            // imprimer les 'etats
            for (State s: states) {
                out.print(" "+s.id+" [");
                if (accept.contains(s))
                    out.print("shape=doublecircle");
                else
                    out.print("shape=circle");
                if (marked!=null && marked.contains(s))
                    out.print(",style=filled");
                out.println("];");
            }
            
            out.println();
            // imprimer les epsilon transitions
            for (State s: states) 
                for (State n: s.epsilon) 
                    out.println(" "+s.id+"->"+n.id+";");
            
            out.println();
            // imprimer les autres transitions 
            for (State s: states) {
                char  c1 = 0;
                State n1 = null;
                for (char c2=0; c2<=256; c2++) {
                    State n2 = (c2<256) ? s.transition[c2] : null;
                    if (n1!=n2) {
                        if (n1!=null) {
                            if (c1==0 && c2==256)
                                label = "\"?\"";
                            else if (c1==c2-1)
                                label = "\""+c1+"\"";
                            else
                                label = "\""+c1+"-"+(c2-1)+"\"";
                            out.println(" "+s.id+"->"+n1.id+"[label="+label+"];");
                        }
                        c1 = c2;
                        n1 = n2;
                    }
                }
            }
            out.println("}");
            out.close();
        } 
        catch (FileNotFoundException e) {
            throw new Error("fichier tmp??.dot n'a pas pu ^etre cr'ee");
        }
    }

Testez avec ce code qui produit un fichier tmp00.dot.

 static public void main(String args[]) {
	Automaton isa = new_WORD("isa");
	isa.dump(null, 0, null);
 }

Puis dans une commande shell visualisez le résultat avec la commande

dot -Tgif -o tmp00.gif tmp00.dot && xv tmp00.gif

Vous devriez voir le graphe suivant, à renommage des sommets près.

Question 3 - Concatenation, Union, Repetition

Ajoutez les fonctions suivantes. Ce n'est pas grave si les paramètres sont modifiés. Pour les deux premières, servez vous de new_WORD.

static Automaton new_EMPTY() // cr'ee un automate qui reconnait le mot vide
static Automaton new_CHAR(char c) // cr'ee un automate qui reconnait un caractère donné
static Automaton new_WILD() // cr'ee un automate qui reconnait un caractère quelconque
static Automaton new_OR(Automaton a1, Automaton a2) // cr'ee un automate qui reconnait l'union des languages rec. par a1 et a2
static Automaton new_SEQ(Automaton a1, Automaton a2) // cr'ee un automate qui reconnait la concaténation des languages
static Automaton new_STAR(Automaton a) // cr'ee un automate qui reconnait la répétition du langage reconnu par a

Testez avec ce code.

 static public void main(String args[]) {
	Automaton a,b,c;
	
	a = new_OR(new_WORD("cafe"),new_WORD("toi"));
	b = new_SEQ(new_WORD("the", new_WORD("sur"));
	c = new_STAR(new_WORD("quoi"));

	a.dump(null, 0, null);
	b.dump(null, 1, null);
	c.dump(null, 2, null);
 }

Question 4 - Reconnaissance de caractères

Ajoutez une méthode boolean match(String word) qui teste si un mot donné est reconnu par l'automate. Pour cela vous avez besoin d'une variable locale

TreeSet<State>
current

, qui contient l'ensemble des états courants, qui initialement ne contient que la cloture par epsilon transitions de l'état initial. Puis sucessivement pour chaque caractère c de la chaîne word vous mettez à jour current : Vous calculez un ensemble next, composé de tous les états qu'on peut atteindre avec une transition avec c sur un état s de current. Faites attention à ne pas mettre dans next l'état poubelle null. Après chaque itération vous remplacerez current par la cloture transitive par epsilon transitions de next. Si à la fin current contient un état acceptant, le mot word est accepté.

Testez avec ce code.

 static final String[] strings = {
	"", "a", "ab", "ac",
	"abc", "acb", "adc",
	"abcd", "abcde",
	"abcdef", "abcdefe", "abcdefef"
 };

 public static void main(String [] args) {
	Automaton a = new_SEQ(new_CHAR('a'), 
                              new_OR( new_SEQ(new_WILD(), new_CHAR('c')), 
	                              new_SEQ(new_WORD("bcd"), new_STAR(new_WORD("ef")))));

	for(String s: strings) {
	    System.out.println("matches " + s + " : " + a.match(s));
	}
 }

Vous devriez avoir le résultat suivant :

java Automaton
matches : false
matches a : false
matches ab : false
matches ac : false
matches abc : true
matches acb : false
matches adc : true
matches abcd : true
matches abcde : false
matches abcdef : true
matches abcdefe : false
matches abcdefef : true

Question 5 - Générer une animation de l'automate

Maintenant à chaque itération appelez

dump(word,
i, current)

, où i et l'indice du caractère traité dans word. Appelez une dernière fois après la boucle

dump(word,
word.length(),
current)

. De cette manière votre programme va générer différents fichiers qui représentent le parcours de l'automate.

Le script shell make_image vous permet de transformer les fichiers produits par le programme en une image GIF animée. On l'exécute avec bash make_image. Vous devriez avoir le résultat suivant. (C'est cool, non ?)

Le corrigé : (Automaton.java) --- à ne consulter qu'après le TD, sinon c'est de la triche