Théorie des langages : Tp automate motifs texte
Télécharger PDFProjet d’informatique théorique 2
Université Bordeaux 1 — Licence Informatique 3ème année (2012-2013)
Objectif du projet
Ce projet vise à développer un logiciel de reconnaissance de motifs dans un texte en exploitant des techniques d’automates étudiées en cours et travaux dirigés.
Les fonctions à implémenter sont décrites ci-dessous. Certaines parties du projet offrent un choix entre la programmation de fonctions et des questions d’ordre théorique.
Modalités de réalisation
Le projet doit être réalisé en binôme. Chaque membre du groupe doit contribuer de manière significative au développement.
Les deux étudiants doivent comprendre les options choisies et les défis rencontrés. Lors de la soutenance (semaines du 1er ou 8 avril), chaque membre présentera sa partie du travail.
La notation peut varier au sein d’un groupe si la répartition du travail est inégale. Tout plagiat sera sanctionné sévèrement.
Un rapport court (3 à 5 pages) doit accompagner le projet. Il doit inclure des exemples, expliquer les difficultés rencontrées et les solutions adoptées.
Date limite de remise du code source et du rapport : 28 mars à 20h, par email à l’adresse indiquée.
Le fichier à transmettre doit être un archive tar.gz contenant un seul dossier portant vos noms. Ce dossier doit inclure :
- le rapport au format PDF nommé rapport.pdf ;
- un répertoire /src/ contenant les fichiers sources du projet.
En cas de questions ou de problèmes, contactez l’équipe pédagogique.
Bibliothèque fournie
Une bibliothèque Python 2.6 est mise à disposition pour manipuler les automates. Elle permet notamment :
- de charger des automates prédéfinis depuis un fichier XML (un exemple est fourni) ;
- de créer des automates directement ;
- d’accéder aux propriétés d’un automate (états, transitions, etc.) ;
- d’afficher graphiquement les automates.
Les transitions ε sont gérées en utilisant une ou plusieurs lettres comme symboles pour ε. Par exemple, le caractère 0 peut représenter ε.
Les ensembles retournés par les fonctions sont de type automaton.pretty_set, une variante de frozenset permettant des manipulations classiques sur les ensembles.
Exemples d’utilisation :
Un automate utilisant des ensembles pour coder ses états peut être construit comme suit :
import automaton
def automate_des_mots_contenant_l_alphabet(alphabet):
initiaux = [automaton.pretty_set()]
epsilons = []
finaux = [automaton.pretty_set(alphabet)]
états = set(automaton.pretty_set())
pile = [automaton.pretty_set()]
transitions = []
while len(pile) > 0:
origine = pile.pop()
for lettre in alphabet:
fin = origine.union([lettre])
if not (fin in états):
états.add(fin)
pile.append(fin)
transitions.append((origine, lettre, fin))
return automaton.automaton(alphabet, epsilons, états, initiaux, finaux, transitions)
Exemples de fonctions disponibles
Voici quelques fonctions utiles de la bibliothèque :
- Aut.has_epsilon_characters() : vérifie si l’automate contient des transitions ε.
- Aut.get_alphabet() : retourne l’alphabet complet de l’automate.
- Aut.get_epsilons() : retourne les lettres représentant ε.
- Aut.get_states(), Aut.get_initial_states(), Aut.get_final_states() : récupèrent les états, états initiaux et états finaux.
- Aut.display() : affiche graphiquement l’automate.
- Aut.delta() et Aut.delta_star() : calculent les successeurs d’un état (ou d’un ensemble d’états) après une transition par une lettre ou un mot.
Travail demandé
Implémentez les fonctions suivantes en utilisant les algorithmes étudiés en cours, sauf pour la déterminisation où l’algorithme vu en TD doit être appliqué. Les automates peuvent être non déterministes et incomplets.
- supprimer_epsilon_transitions(Aut) : génère un automate équivalent sans transitions ε.
- completer(Aut) : retourne l’automate complété de Aut.
- determinisation(Aut) : calcule l’automate déterminisé à partir de Aut.
- union(Aut1, Aut2), intersection(Aut1, Aut2) : construisent des automates pour l’union et l’intersection des langages reconnus par Aut1 et Aut2.
- complement(Aut) : calcule le complément du langage reconnu par Aut.
- miroir(Aut) : retourne l’automate miroir de Aut, où les transitions sont inversées, les états initiaux deviennent finaux et vice versa.
- minimiser(Aut) : génère l’automate minimal de Aut en utilisant l’algorithme de Moore ou du double renversement.
- expression_vers_automate(E) : convertit une expression rationnelle en format préfixe (sous forme de liste) en un automate minimal équivalent. L’algorithme de Thomson est recommandé.
Partie à choix
Deux options sont proposées pour compléter le projet :
- Démontrer l’algorithme du double renversement (destiné aux étudiants en math-info).
- Développer un analyseur d’expressions rationnelles, transformant une chaîne de caractères comme (a+b*c)* en une liste Python de la forme [“*”, [“+”, [“a”], [“*”, “b”, “c”]]].
Installation de la bibliothèque
Pour utiliser la bibliothèque sur votre machine, suivez ces étapes :
- Installez Python (version 2.6 ou supérieure).
- Installez GraphViz.
- Téléchargez les fichiers automaton.py et automaton.html.
Sous Debian et Ubuntu
Python est déjà installé sur ces systèmes. Installez GraphViz via la commande :
sudo apt-get install graphviz
Téléchargez ensuite les fichiers automaton.py et automaton.html.
Sous MacOSX
Installez GraphViz en téléchargeant le paquet correspondant à votre version de macOS.
Téléchargez ensuite les fichiers automaton.py et automaton.html.
Sous Windows
Installez Python en téléchargeant le fichier d’installation adapté à votre système.
Installez GraphViz et ajoutez les répertoires des exécutables de Python et de GraphViz à la variable d’environnement PATH.
Pour modifier PATH :
- Cliquez droit sur Ordinateur, puis Propriétés.
- Sélectionnez Paramètres système avancés.
- Accédez à Variables d’environnement.
- Modifiez la variable Path en ajoutant les chemins suivants :
;C:\Program Files (x86)\Graphviz2.30\bin;C:\Python33
Téléchargez ensuite les fichiers automaton.py et automaton.html.
FAQ
Comment gérer les transitions ε dans un automate ?
Les transitions ε sont représentées par une ou plusieurs lettres définies dans l’argument epsilons lors de la création de l’automate.
Quelle méthode utiliser pour la déterminisation ?
L’algorithme vu en cours et travaux dirigés doit être appliqué strictement pour la déterminisation.
Comment coder une expression rationnelle en format préfixe ?
L’expression (a+b*c)* doit être représentée sous forme de liste imbriquée : [“*”, [“+”, [“a”], [“*”, “b”, “c”]]].