Local languages and the Berry-Sethi algorithm

J. Berstel, J-E. Pin

IBP-Litp 1995/13: Rapport de Recherche Litp / Litp research reports
7 pages - Février/February 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Local languages and the Berry-Sethi algorithm

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 an exposition and a formal proof of the background for the algorithm of Berry and Sethi relating the computation involved to a well-known family of recognizable languages, the local languages.

Publications internes Litp 1995 / Litp research reports 1995