Regular closure of deterministic languages

Citation
E. Bertsch et Mj. Nederhof, Regular closure of deterministic languages, SIAM J COMP, 29(1), 1999, pp. 81-102
Citations number
16
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
29
Issue
1
Year of publication
1999
Pages
81 - 102
Database
ISI
SICI code
0097-5397(19990922)29:1<81:RCODL>2.0.ZU;2-L
Abstract
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 th e class of deterministic languages with the prefix property or, stated in a n equivalent way, all LR(k) languages are in the regular closure of the cla ss of LR(0) languages.