Des Codes Barres pour les Langages Rationnels

Regular expressions and finite automata represent regular languages. The link between these two mathematical structures is the subject of many research topics. Each one of these models gets advantages and inconveniences. In this document, new regular operators are defined, the multitildes- bars, which create a new expression model falling in the range of finite automata to simple regular expressions, which uses concatenation, union, and Kleene's star. Multi-tildes-bars are based on simple regular operations, namely the adjunction or the elimination of the empty word. Several classical conversions between simple regular expressions and finite automata are extended to these new operators. Finally, we show that these new expressions have an exponential factorization power with respect to the one of simple regular expressions. KeywordsLes 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