TOWARDS AN ALGEBRAIC THEORY OF CONTEXT-FREE LANGUAGES

Article type: Research Article

Authors: Berstel, J. | Boasson, L.

Affiliations: LITP, Institut Blaise Pascal, Université Pierre et Marie Curie, 4, place Jussieu, F-75252 Paris Cedex 05, France | LITP, Université Denis Diderot, 2, place Jussieu, F-75251 Paris Cedex 05, France

Note: [] Partially supported by the PRC “Mathématiques et Informatique” and by ESPRIT BRA working group 6317 – ASMICS 2.

Abstract: The purpose of the paper is to present the implications of a new definition of context-free languages. The main interests of this approach are first to allow full formal proofs and second to enlight the crucial role of rational closures. The proposed formalism is based on a theorem of Wechler. It is very near to the “radical algebras” of Conway.

DOI: 10.3233/FI-1996-253401

Journal: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 217-239, 1996