Local languages and the Berry-Sethi algorithm

被引：25

作者：

Berstel, J ^{[1
]}

Pin, JE ^{[1
]}

机构：

[1] INST BLAISE PASCAL, LITP, F-75252 PARIS, FRANCE

来源：

THEORETICAL COMPUTER SCIENCE | 1996年 / 155卷 / 02期

关键词：

D O I：

10.1016/0304-3975(95)00104-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：439 / 446

页数：8

共 13 条

[1]

Aho Alfred V., 1986, ADDISON WESLEY SERIE

[2] FROM REGULAR EXPRESSIONS TO DETERMINISTIC AUTOMATA [J].

BERRY, G ;

SETHI, R .

THEORETICAL COMPUTER SCIENCE, 1986, 48 (01) :117-126

[3]

BERSTEL J, 1987, LECT NOTES COMPUTER, V386, P2

[4]

BRUGGEMANNKLEIN A, 1992, LECT NOTES COMPUT SC, V583, P87

[5]

BRUGGEMANNKLEIN A, 1992, LECT NOTES COMPUT SC, V577, P173

[6]

CHAMPARNAUD JM, IN PRESS INFORM PROC

[7]

Eilenberg S., 1974, AUTOMATA LANGUAGES M, V59

[8]

Glushkov V M, 1961, Russian Mathematical Survey, V16, P1, DOI DOI 10.1070/RM1961V016N05ABEH004112

[9]

McNaughton R., 1960, IEEE TRANS ELECTRON, V9, P39, DOI [10.1109/TEC.1960.5221603, DOI 10.1109/TEC.1960.5221603]

[10] TRANSDUCTION OF CHOMSKY LANGUAGES [J].

NIVAT, M .

ANNALES DE L INSTITUT FOURIER, 1968, 18 (01) :339-&

← 1 2 →