Computing ε-free NFA from regular expressions in .O(nlog2(n)) time

被引:30
作者
Hagenah, C [1 ]
Muscholl, A [1 ]
机构
[1] Univ Stuttgart, Inst Informat, D-70565 Stuttgart, Germany
来源
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS | 2000年 / 34卷 / 04期
关键词
epsilon-free-nondeterministic automata; regular expressions; common follow sets construction;
D O I
10.1051/ita:2000116
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The standard procedure to transform a regular expression of size n to an epsilon -free nondeterministic finite automaton yields automata with O(n) states and O(n(2)) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic et al. showed how to build an epsilon -free NFA with only O(n log(2)(n)) transitions. The current lower bound on the number of transitions is Omega (n log(n)). A rough running time estimation for the common follow sets (CFS) construction proposed by Hromkovic et al. yields a cubic algorithm. In this paper we present a sequential algorithm for the CFS construction which works in time O(n log(n)+ size of the output). On a CREW PRAM the CFS construction can be performed in time O(log(n)) using O(n + (size of the output)/ log(n)) processors. We also present a simpler proof of the lower bound on the number of transitions.
引用
收藏
页码:257 / 277
页数:21
相关论文
共 13 条
[1]   FROM REGULAR EXPRESSIONS TO DETERMINISTIC AUTOMATA [J].
BERRY, G ;
SETHI, R .
THEORETICAL COMPUTER SCIENCE, 1986, 48 (01) :117-126
[2]   Local languages and the Berry-Sethi algorithm [J].
Berstel, J ;
Pin, JE .
THEORETICAL COMPUTER SCIENCE, 1996, 155 (02) :439-446
[3]   REGULAR EXPRESSIONS INTO FINITE AUTOMATA [J].
BRUGGEMANNKLEIN, A .
THEORETICAL COMPUTER SCIENCE, 1993, 120 (02) :197-213
[4]   COMPLEXITY MEASURES FOR REGULAR EXPRESSIONS [J].
EHRENFEUCHT, A ;
ZEIGER, P .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 12 (02) :134-146
[5]  
GIBBONS A, 1989, EFFICIENT PARALLEL A
[6]  
Glushkov V M, 1961, Russian Mathematical Survey, V16, P1, DOI DOI 10.1070/RM1961V016N05ABEH004112
[7]  
Hagenah C, 1998, LECT NOTES COMPUT SC, V1450, P277, DOI 10.1007/BFb0055777
[8]  
Hromkovic J, 1997, LECT NOTES COMPUT SC, V1200, P55, DOI 10.1007/BFb0023448
[9]  
Jaja J., 1992, INTRO PARALLEL ALGOR
[10]  
McNaughton R., 1960, IEEE TRANS ELECTRON, V9, P39, DOI [10.1109/TEC.1960.5221603, DOI 10.1109/TEC.1960.5221603]