Regular closure of deterministic languages

被引：14

作者：

Bertsch, E

Nederhof, MJ

机构：

[1] Ruhr Univ Bochum, D-4630 Bochum, Germany

[2] DFKI, D-66123 Saarbrucken, Germany

来源：

SIAM JOURNAL ON COMPUTING | 1999年 / 29卷 / 01期

关键词：

context-free languages; regular languages;

D O I：

10.1137/S009753979528682X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We recall the notion of regular closure of classes of languages. We present two important results. The first result is that all languages which are in the regular closure of the class of deterministic (context-free) languages can be recognized in linear time. This is a nontrivial result, since this closure contains many inherently ambiguous languages. The second result is that the class of deterministic languages is contained in the closure of the class of deterministic languages with the prefix property or, stated in an equivalent way, all LR(k) languages are in the regular closure of the class of LR(0) languages.

引用

页码：81 / 102

页数：22

共 16 条

[1] TIME AND TAPE COMPLEXITY OF PUSHDOWN AUTOMATON LANGUAGES [J].

AHO, AV ;

HOPCROFT, JE ;

ULLMAN, JD .

INFORMATION AND CONTROL, 1968, 13 (03) :186-&

[2] RECOGNIZING SUBSTRINGS OF LR(K) LANGUAGES IN LINEAR-TIME [J].

BATES, J ;

LAVIE, A .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1994, 16 (03) :1051-1077

[3]

Berstel J., 1979, TEUBNER STUDIENBUCHE, V38

[4]

BERTSCH E, 1994, 176 RUHR U BOCH FAK

[5]

BERTSCH E, 1995, 186 RUHR U BOCH FAK

[6] AN EFFICIENT CONTEXT-FREE PARSING ALGORITHM [J].

EARLEY, J .

COMMUNICATIONS OF THE ACM, 1970, 13 (02) :94-&

[7]

HARRISON MA, 1978, INTRO FORMAL LANGUAG

[8]

Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation

[9]

Knuth D. E., 1977, SIAM Journal on Computing, V6, P323, DOI 10.1137/0206024

[10]

Lang Bernard, 1974, LECT NOTES COMPUTER, P255, DOI [DOI 10.1007/3-540-06841-4_65, 10.1007/978-3-662-21545-6, DOI 10.1007/978-3-662-21545-6]

← 1 2 →