Résumé : La construction efficace d'un automate fini
à partir d'une expression rationnelle (régulière) est
l'une des tâches principales de la construction d'un compilateur et
du traitement de documents ou d'hypertextes. Le but de cet article est de
présenter une preuve formelle de l'algorithme de Berry et Sethi qui
met en évidence les liens entre cet algorithme et une famille bien
connue de langages reconnaissables, les langages locaux.
Abstract : One of the basic tasks in compiler construction, document
processing, hypertext software and similar projects is the efficient
construction of a finite automaton from a given rational (regular)
expression. The aim of the present paper is to give a formal proof of the
algorithm of Berry and Sethi and to emphasize the links between this
algorithm and a well-known family of recognizable languages, the local
languages.