Name
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 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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1137/S009753979528682X | SIAM J. Comput. |
Keywords | Field | DocType |
prefix property,nontrivial result,deterministic languages,ambiguous language,regular closure,deterministic language,important result,linear time,regular languages,context free languages | Discrete mathematics,Formal language,Nested word,Deterministic pushdown automaton,Abstract family of languages,Deterministic context-free language,Cone (formal languages),Pumping lemma for regular languages,Pumping lemma for context-free languages,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 1 | 0097-5397 |
Citations | PageRank | References |
9 | 0.77 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eberhard Bertsch | 1 | 63 | 26.54 |
| Mark-jan Nederhof | 2 | 387 | 53.30 |