Théorie des langages : Tp automate motifs texte
Télécharger PDFProjet d’informatique théorique 2
Université Bordeaux 1 — 2012-2013
Licence Informatique 3ème année
L’objectif du projet est de réaliser un logiciel de reconnaissance de motifs dans un texte en
utilisant des techniques vues en cours et TD sur les automates. Les fonctions à écrire sont détaillées
ci-dessous. Une partie de ce projet présente un choix entre l’écriture de certaines fonctions et des
questions de nature plus théorique.
Pour manipuler les automates, il est fourni une interface en Python. Elle permet d’accélérer le
développement du projet, en ne se concentrant que sur les algorithmes. Il est permis d’utiliser un
autre langage (C, Java par exemple). Dans ce cas, informez votre enseignant de TD du langage dans
lequel vous souhaitez programmer.
1 Modalités de réalisation
Le projet est à réaliser par groupe de 2 personnes. Chacun des membres d’un groupe doit réaliser
une partie significative du travail demandé. L’écriture seule du rapport, par exemple, est insuffisante.
Les 2 membres d’un groupe doivent connaître les options générales choisies ainsi que les difficultés
rencontrées. Chacun devra exposer individuellement sa contribution lors de la soutenance (semaines
du 1er ou 8 avril). La notation pourra varier à l’intérieur d’un groupe en cas de travail trop inégal,
et tout plagiat détecté sera sévèrement sanctionné.
Le projet sera présenté dans un court rapport (3 à 5 pages) illustré par des exemples, exposant
les problèmes rencontrés et les choix effectués pour les résoudre.
Date limite de remise du source et du rapport par mail à it2@labri.fr :28 mars à 20h.
Le fichier transmis doit être un fichier de type.tar.gzcontenant un seul répertoire à vos noms,
dans lequel se trouvera :
– le fichier du rapport sous forme pdf :rapport.pdf.
– un répertoire./src/contenant les sources du projet.
En cas de difficultés ou de questions, n’hésitez pas à contacter l’équipe pédagogique it2@labri.fr.
2 La bibliothèque fournie
Une bibliothèque compatible Python 2.6 vous est fournie. Cette section la présente rapidement.
Elle permet entre autres :
–de charger des automates prédéfinis dans un fichier de type XML. Un exemple de tel fichier
est fourni ;
– de créer des automates directement ;1 –d’accéder aux différentes caractéristiques d’un automate, de récupérer les successeurs d’un état
par une lettre, etc.
– d’afficher les automates.
La bibliothèque se trouve dans le fichierautomaton.pyfourni sur le site du cours à l’addresse :
∼zeitoun/enseignement/12-13/AS+IT2.
Cette bibliothèque est documentée : pour accéder à l’aide sous python, il suffit de taperhelp(),
puisautomaton. Les fonctions sont décrites et présentées avec des exemples. Il est aussi possible de
consulter la documentation à l’aide d’une navigateur web en lisant le fichierautomaton.html.
La plupart des fonctions sont faciles à comprendre. Un point particulier est la gestion desε-
transitions : pour les représenter, on décide d’une ou plusieurs lettres jouant le rôle d’ε. Par exemple,
le code suivant permet de créer et d’afficher un automate dans lequel le caractère’0’est utilisé pour
représenterε.
import automaton
aut1 = automaton . automaton (
e p s i l o n s = [ ’ 0 ’ ] ,
s t a t e s = [ 5 ] , i n i t i a l s = [ 0 , 1 ] , f i n a l s = [ 3 , 4 ] ,
t r a n s i t i o n s =[
(0 , ’ a ’ , 1 ) , (1 , ’ b ’ , 2 ) , (2 , ’ b ’ , 2 ) , (2 , ’0 ’ ,3) , (3 , ’ a ’ , 4 )] )
aut1 . display ()
Plusieurs lettres peuvent être interprétées comme desε-transitions dans un même automate. Les
ensembles d’états ou de lettres retournés par les fonctions sont de typeautomaton.pretty_setqui
hérite defrozenset, permettant les manipulations habituelles sur les ensembles.
Voirl#frozenset.
En utilisantautomaton.pretty_set, il est possible d’utiliser des ensembles pour coder les états
d’un automate. Par exemple, si l’on note parAl’alphabet, voici un programme qui construit
l’automate qui reconnaît l’ensemble des mots possédant toutes les lettres deA:
import automaton
def automate_des_mots_contenant_l_alphabet ( alphabet ) :
i n i t i a u x = [ automaton . pretty_set () ]
e p s i l o n s = [ ]
finaux = [ automaton . pretty_set ( alphabet ) ]
états = set ( automaton . pretty_set () )
p i l e = [ automaton . pretty_set () ]
t r a n s i t i o n s = [ ]
while len ( p i l e ) > 0:
o r i g i n e = p i l e . pop ()
f o r l e t t r e in alphabet :
f i n = o r i g i n e . union ( [ l e t t r e ] )
i f not ( f i n in états ) :
états . add ( f i n )
p i l e . append ( f i n )2 t r a n s i t i o n s . append ( ( origine , l e t t r e , f i n ) )
return automaton . automaton (
alphabet , epsilons , états , initiaux , finaux , t r a n s i t i o n s) A = automate_des_mots_contenant_l_alphabet ( [ ’ a ’ , ’ b ’ , ’ c ’ ] )
A. display ()
Ce programme affiche l’automate suivant :c bc acb bb bc cac baca ba aa ac b
{a, c, b}{a}{b} {c, b}{} {c}
{a, c}{a, b}
Il est aussi possible d’utiliser des tuples pour coder les états d’un automate. Par exemple, voici le
programme qui construit un automate qui reconnaît tout les motsmde{a, b, c, d}∗ tel que pour
tout préfixewdemon ait||w|a −|w|b |≤1et||w|c −|w|d |≤1.
import automaton
def automate ( ) :
alphabet = [ ’a ’ , ’b ’ , ’ c ’ , ’d ’ ]
e p s i l o n s = [ ]
i n i t i a u x = [ (0 ,0) ]
états = [ ]
finaux = [ ]
t r a n s i t i o n s = [ ]
f o r a_moins_b in [0 ,1 ,−1]:
f o r c_moins_d in [0 , 1 ,−1]:
états . append ( (a_moins_b , c_moins_d) )
finaux . append ( (a_moins_b , c_moins_d) )
f o r o r i g i n e in états :
f o r l e t t r e in alphabet :
i f l e t t r e ==’a ’ :
f i n = ( o r i g i n e [0]+1 , o r i g i n e [ 1 ] )
e l i f l e t t r e ==’b ’ :
f i n = ( o r i g i n e [0]−1 , o r i g i n e [ 1 ] )
e l i f l e t t r e ==’c ’ :3 f i n = ( o r i g i n e [ 0 ] , o r i g i n e [1]+1 )
e l s e :
f i n = ( o r i g i n e [ 0 ] , o r i g i n e [1]−1 )
i f abs ( f i n [0]) <=1 and abs ( f i n [1]) <=1 :
t r a n s i t i o n s . append ( ( origine , l e t t r e , f i n ) )
return automaton . automaton (
alphabet , epsilons , états , initiaux , finaux , t r a n s i t i o n s) B = automate ( )
B. display ()
Ce programme affiche l’automate suivant :b bd cb aac ab dd aa bd da cb cc dc (0, 1)
(0, 0)
(-1, 1)(-1, -1)
(-1, 0)
(1, 0)
(0, -1)
(1, 1)
(1, -1)
Quelques exemples de fonctions
Cette section décrit quelques fonctions disponibles dans la bibliothèque. Pour l’aide complète :
help()puisautomaton. Il est conseillé de lire le fichierautomaton.pyavant de commencer à
travailler. Les fonctions ont en général des arguments optionnels qui changent leur comportement par4 défaut. Par exemple, on peut préciser pour la fonctiondisplay()qui affiche un automate un titre
de figure, et un booléen permettant d’attendre ou non que l’utilisateur ferme la fenêtre graphique
pour continuer. Consulter l’aide pour connaître les options éventuelles. Les premières fonctions à
comprendre sont les suivantes :
–Aut.has_epsilon_characters(): teste si l’automateAuta desε-transitions.
–Aut.get_alphabet(): retourne l’alphabet complet de l’automateAut.
–Aut.get_epsilons(): retourne l’ensemble des lettres représentantεdansAut.
–Aut.get_states()
,Aut.get_initial_states()etAut.get_final_states()retournent les
ensembles d’états, d’états initiaux et d’états finaux deAut.
–Aut.display(): dessine et affiche l’automateAut.
–Aut.delta()
etAut.delta_star(): calculent les successeurs d’un d’état (ou plus généralement
d’un ensemble d’états) par une lettre (pourdelta()) ou un mot (pourdelta_star()). La
documentation explique comment sont traitées lesε-transitions.
3 Travail demandé
Il est demandé d’écrire les fonctions suivantes (les algorithmes utilisés sont au choix, sauf pour la
déterminisation). Les automates arguments peuvent être non déterministes et/ou incomplets.– Une fonctionsupprimer_epsilon_transitions( Aut )qui calcule à partir de l’automate
Autun automate équivalent sansε-transitions.
– Une fonctioncompleter( Aut )qui et retourne l’automate complété de l’automateAut.
–Une fonctiondeterminisation( Aut )qui et retourne l’automate déterminisé calculé à partir
de l’automateAut, en suivant l’algorithme vu en cours et TD.
–Des fonctionsunion( Aut1, Aut2 ),intersection( Aut1, Aut2 )calculant des automates
pour l’union et l’intersection des langages reconnus par les automates deAut1etAut2, ainsi
qu’un automatecomplement( Aut )calculant le complément du langage reconnu parAut.– Une fonctionmiroir(Aut)qui calcule l’automate miroir d’un automateAut: il est obtenu en
retournant les flèches, en déclarant initiaux les états qui étaient finaux dansAutet en déclarant
finaux les états qui étaient initiaux dansAut.
–Une fonctionminimiser( Aut )qui calcule l’automate minimal de l’automateAut. On pourra
utiliser soit l’algorithme de Moore, soit l’algorithme du double renversement.
–Une fonctionexpression_vers_automate( E )qui prend en argument une expression ration-
nelle et qui construit l’automate minimal équivalent à cette expression. On pourra utiliser
l’algorithme de Thomson, plus rapide à écrire que celui de Glushkov.
L’expression sera codée en format préfixe, sous forme de liste : par exemple, l’expression(a+b ∗a) ∗
sera représentée par la listeE=["*", ["+", ["a", [".", ["*","b"], ["a"]]]]].
Partie à choix
Pour terminer, 2 choix sont proposés :
1. Montrer l’algorithme du double renversement (plutôt destiné aux étudiants math-info).
2.Écrire un analyseur d’expressions rationnelles, qui convertit les expressions rationnelles (données
comme chaînes de caractères de la forme(a+b∗a)∗) en listes Python (de la forme["*",
["+", ["a", [".", ["*","b"], ["a"]]]]]).5 A Installer la biliothèque d’automate sur son ordinateur
Pour utiliser la bibliothèque sur votre ordinateur, vous devez :
– Installer Python (au moins la version 2.6)
– Installer GraphViz
– Télécharger la bibliothèque automaton.py
A.1 Sous debian et ubuntu
Python est déjà installé sous Ubuntu et Debian.
Il ne vous reste plus qu’à installer graphviz en tapant la ligne de commande suivante :
sudo apt−get i n s t a l l graphviz
Vous pouvez maintenant télécharger la bibliothèqueautomaton.pyet sa documentationautomaton.html
présent à l’adresse :
∼zeitoun/enseignement/12-13/AS+IT2
A.2 Sous MacOSX
Python est déjà installé sous Ubuntu et Debian.
Pour installer GraphViz, vous devez installer le paquet correspondant à votre version du système
d’exploitation présent à l’adresse :. Il ne vous reste plus qu’à télécharger la bibliothèqueautomaton.pyet sa documentation
automaton.htmlsituée à l’adresse :
∼zeitoun/enseignement/12-13/AS+IT2
A.3 Sous Windows
Pour installer Python, vous devez installer le paquet d’installation (correspondant à votre version
du système d’exploitation) présent à l’adresse :
download/.
Pour installer GraphViz, vous devez installer le paquet (correspondant à votre version du système
d’exploitation) situé à l’adresse :. Ajouter dans la variable d’environement PATH de windows, les répertoires des éxecutables de
python et de graphviz. Pour ce faire, vous devez éditer la valeur de la variable PATH qui se trouve à :
demarre->ordinateur(click droit)->propriétés->Modifier les paramètres->
Paramètres Système avancés ->Variables d’environnements->Variables systèmes->Path->
Modifier6 en ajoutant à la fin de la ligne, le texte suivant :
;C: Program F i l e s ( x86 )\ Graphviz2 .30\ bin ;C:\ Python33
(si vous avez téléchargé la version 2.30 de GraphViz et la version 3.3 de Python).
Il ne vous reste plus qu’à télécharger la bibliothèqueautomaton.pyet sa documentation
automaton.htmlprésente à l’adresse :
∼zeitoun/enseignement/12-13/AS+IT2
7