Conception et implémentation d’un générateur automatique d’automates d’états finis déterministes et leurs représentations graphiques, à partir d’expressions régulières
Loading...
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Université Mouloud Mammeri
Abstract
Pour participer à l'effort de développement d'outils logiciels facilitant la description et la reconnaissance de langages formels, on se propose dans ce projet de concevoir et d'implémenter un outil permettant de faciliter la spécification des langages réguliers et d'automatiser le processus de construction d'automates ainsi que leurs représentation graphiques sous formes d'images. En d'autres termes, il s'agit de concevoir et d'implémenter un générateur automatique d'automates d'états finis simples et déterministes à partir d'une expression régulière. La réalisation de ce projet nous a été très enrichissante dans la mesure où elle nous à permis d'approfondir nos connaissances en théorie des langages formels. Elle nous à permis aussi de mesurer la puissance des expressions régulières et des grammaires formelles dans la description et des automates finis dans la reconnaissance de ces langages qui sont à la base de tous les langages informatiques. Ce projet nous a aidé à adopter une vision conceptuelle dans l'organisation des données lors de l'implémentation des différents algorithmes, en nous confrontant à l'automatisation du traitement, de l'analyse et de la reconnaissance. Ce projet nous a permit également de maîtriser d'avantage le système GNU/Linux ainsi qu'une multitude d'outils tels que ceux de la chaîne de compilation gcc, les outils Fex, yacc, make et graphviz, très utilisés par les chercheurs et développeurs à travers le monde. Notre travail ouvre plusieurs perspectives notamment l'implémentation de la procédure de minimisation qui permettra d'optimiser les ressources en espace mémoire et en temps d'exécution. Le générateur qui en résulterait fera correspondre à chaque DFA un DFA minimal ayant moins d'états et transitions et reconnaissant le même langage.
Description
49 f. : ill. ; 30 cm. (+ CD-Rom)
Keywords
Longage formels, Expressions reguliéres Automatic
Citation
Réseaux Mobilité Et Systèmes Embarqués