Les expressions rationnelles et les automates finis sont des objets mathématiques permettant de représenter les langages rationnels. Le lien entre ces structures est le sujet de nombreux thèmes de recherche. Chacun de ces modèles présentent avantages et inconvénients. Nous nous proposons d'établir de nouveaux opérateurs, les multi-tildes-barres, permettant de créer un modèle d'expression se situant entre la structure d'automate et celle d'expression rationnelle simple, utilisant l'union, la concaténation, et l'étoile de Kleene. Les multi-tildes-barres sont basées sur des opérations relativement simples sur les langages, l'ajout et l'élimination du mot vide. Nous étendons les méthodes de conversion classiques entre expressions rationnelles simples et automates finis aux expressions utilisant ces nouveaux opérateurs. Nous montrons également que le pouvoir de factorisation de ces nouvelles expressions est exponentiellement plus grand que celui des expressions rationnelles simples.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00794580 |
| Date | 15 October 2010 |
| Creators | Mignot, Ludovic |
| Publisher | Université de Rouen |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds