Feedback

Faculté des Sciences
Faculté des Sciences
MASTER THESIS
VIEW 61 | DOWNLOAD 12

Conversions effectives entre expressions régulières et automates finis

Download
Fauville, Stéphane ULiège
Promotor(s) : Rigo, Michel ULiège
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 ULiège
Date of defense  : 9-Sep-2016
Advisor(s) : Rigo, Michel ULiège
Committee's member(s) : Boigelot, Bernard ULiège
Charlier, Emilie ULiège
Lecomte, Pierre ULiège
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)

File
Access mémoire.pdf
Description:
Size: 530.86 kB
Format: Adobe PDF

Annexe(s)

File
Access Automaton.java
Description:
Size: 11.81 kB
Format: Unknown
File
Access Regex.java
Description:
Size: 9.04 kB
Format: Unknown
File
Access State.java
Description:
Size: 4.48 kB
Format: Unknown
File
Access Transition.java
Description:
Size: 2.08 kB
Format: Unknown
File
Access Example.java
Description:
Size: 2.5 kB
Format: Unknown

Author

  • Fauville, Stéphane ULiège Université de Liège > Master sc. math., fin. spéc. infor. (ex 2e ma.)

Promotor(s)

Committee's member(s)

  • Boigelot, Bernard ULiège Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique
    ORBi View his publications on ORBi
  • Charlier, Emilie ULiège Université de Liège - ULg > Département de mathématique > Mathématiques discrètes
    ORBi View his publications on ORBi
  • Lecomte, Pierre ULiège Université de Liège - ULg > Département de mathématique > Géométrie et théorie des algorithmes
    ORBi View his publications on ORBi
  • Total number of views 61
  • Total number of downloads 12










All documents available on MatheO are protected by copyright and subject to the usual rules for fair use.
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.