Local languages and the Berry-Sethi algorithm. (English) Zbl 0872.68116

Summary: 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 G. Berry and R. Sethi, [Theor. Comput. Sci. 48, 117-126 (1986; Zbl 0626.68043)]relating the computation involved to a well-known family of recognizable languages, the local languages.


68Q45 Formal languages and automata


Zbl 0626.68043
Full Text: DOI


[1] Aho, A.V.; Sethi, R.; Ullman, J., Compilers: principles, techniques and tools, ()
[2] Berry, G.; Sethi, R., From regular expressions to deterministic automata, Theoret. comput. sci., 48, 117-126, (1986) · Zbl 0626.68043
[3] Berstel, J., Finite automata and rational languages, an introduction, (), 2-14
[4] Brüggemann-Klein, A., Regular expressions into finite automata, (), 87-98
[5] Brüggemam-Klein, A.; Wood, D., Deterministic regular languages, (), 173-184
[6] J.M. Champarnaud, From a regular expression to an automaton, Inform. Process. Lett., to appear. · Zbl 0915.68086
[7] Eilenberg, S., ()
[8] Glushkov, V.M., The abstract theory of automata, Russian math. surveys, 16, 1-53, (1961) · Zbl 0104.35404
[9] McNaughton, R.; Yamada, H., Regular expressions and state graphs for automata, IEEE trans. electronic comput., 9, 39-47, (1960) · Zbl 0156.25501
[10] Nivat, M., Transductions des langages de chomsky, Ann. Fourier, 18, 339-455, (1968) · Zbl 0313.68065
[11] Watson, B.W., A taxonomy of finite automata construction algorithms, () · Zbl 0858.68026
[12] Watson, B.W., A taxonomy of finite automata minimization algorithms, () · Zbl 0858.68026
[13] D. Ziadi, J.L. Ponty and J.-M. Champarnaud, Passage d́une expression rationnelle à un automate fini non-déterministe, Bull. Belgian Math. Soc. Simon Stevin, to appear. · Zbl 0915.68123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.