Conversions effectives entre expressions régulières et automates finis
Fauville, Stéphane
Promotor(s) : Rigo, Michel
Date of defense : 9-Sep-2016 • Permalink : http://hdl.handle.net/2268.2/1609
Details
Title : | Conversions effectives entre expressions régulières et automates finis |
Author : | Fauville, Stéphane |
Date of defense : | 9-Sep-2016 |
Advisor(s) : | Rigo, Michel |
Committee's member(s) : | Boigelot, Bernard
Charlier, Emilie Lecomte, Pierre |
Language : | French |
Number of pages : | 52 |
Discipline(s) : | Physical, chemical, mathematical & earth Sciences > Mathematics |
Institution(s) : | Université de Liège, Liège, Belgique |
Degree: | Master en sciences mathématiques, à finalité spécialisée en informatique |
Faculty: | Master thesis of the Faculté des Sciences |
Abstract
[fr] Ce mémoire s'articule autour de quatre chapitres. Le premier constitue un rappel sur les expressions régulières et les automates. Il contient quelques définitions essentielles et une introduction au théorème de Kleene. Le deuxième chapitre présente la méthode des dérivées et des dérivées partielles pour passer d'une expression régulière à un automate fini. Le troisième chapitre décrit la méthode de suppression d'états pour passer d'un automate à une expression régulière. De plus, on présente également deux heuristiques pour tenter d'obtenir une expression plus courte. Il s'agit de l'heuristique des ponts par Han et Wood et de l'heuristique des poids par Delgado et Morais. Enfin, le quatrième et dernier chapitre est une succincte explication de l'implémentation réalisée. On y présente les choix de représentations et quelques commentaires sur l'utilisation du code.
File(s)
Document(s)
Annexe(s)
Cite this master thesis
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.