Automates
finis
Ces TDs et TPs portent sur le cours de Jean-Marie Rifflet.
Merci aux "anciens" pour leur travail, qui a facilité le
nôtre.
Énoncés de TP
Le TP1 (.ps,.pdf)
portait sur les mots en Java.
Le TP2 (.ps,.pdf)
était une révision, via les mots, de certaines notions
essentielles de Java : héritage, récursion...
Le TP3 (.ps,.pdf)
abordait enfin la représentation des automates en JAVA.
Le TP4 (.ps,.pdf)
portait sur le même sujet, en proposant d'aller un peu plus loin
pour ceux qui le désirent.
Le TP5 (.ps,.pdf)
portait toujours sur le même sujet, avec une ouverture vers les
automates non déterministes.
Le TP6 (.ps,.pdf)
introduisait les opérations sur les automates
déterministes, avant d'aborder le cas non déterministe.
Le TP7 (.ps,.pdf)
était un TP noté, qui traitait de la reconnaissance
non-déterministe.
Le TP8 (.ps,.pdf)
abordait l'implémentation de l'algorithme de
déterminisation.
Le TP9 était constitué de deux sujets : l'un (.ps,.pdf)
continuait avec l'algortihme de déterminisation ; l'autre (.ps,.pdf)
abordait les epsilon-transitions et la question de
l'égalité entre deux automates.
Le TP10 était constitué de sujets quasi-identiques
à ceux du TD9 : le premier (.ps,.pdf) concernait l'algortihme de
déterminisation, le deuxième (.ps,.pdf) les epsilon-transitions, la
question de
l'égalité entre deux automates et la minimisation.
Corrections de TP
Automates déterministes, lecture/écriture
dans un fichier : corrLE.java (le
fichier corrAD.java est
obsolète)
Fichiers de tests : test.auto, test2.auto
Automates non déterministes : corrND.java.
Pour l'utiliser, après compilation tapez "java Automate abc" où abc est le mot à tester sur
chacun des deux automates.
Fichier de test : test3.auto
Énoncés de TD
ATTENTION : Le TD a
lieu en salle 9 du RdC 33-34,
c'est-a-dire EN-DESSOUS du niveau Jussieu (et non pas dans le patio).
Le TD1 (.ps,.pdf)
proposait quelques exercices plus ou moins faciles sur les mots.
Le TD2 (.ps,.pdf)
attaquait les résidus, quelques exercices faciles sur les
automates et la question de la représentation des listes en JAVA.
Le TD3 (.ps,.pdf)
abordait en douceur les automates.
Le TD4 (.ps,.pdf)
allait plus loin : il se finissait par le redoutable lemme
d'itération (ou lemme de l'étoile).
Le TD5 (.ps,.pdf)
parlait des langages reconnaissables : lemme d'itération versus
expressions rationnelles, un combat sans merci...
Le TD6 (.ps,.pdf)
nous lançait à l'assaut de l'algorithme de
déterminisation.
Le TD7 (.ps,.pdf)
proposait quelques révisions, avant d'aborder le lemme d'Arden
et l'algorithme de Mc-Naughton et Yamada. Il s'est terminé par
une interro.
Le TD8 (.ps,.pdf)
proposait encore quelques révisions avant le partiel.
Le TD9 (.ps,.pdf)
concernait à la fois le lemme d'Arden, la méthode de
McNaughton-Yamada, la suppression des epsilon-transitions et l'automate
de Thompson.
Le TD10 (.ps,.pdf)
expliquait la déterminisation. Il s'est terminé par
une interro.
Page
du
cours