##
An innovative finite-state concept for recognition and parsing of
context-free languages

** Eberhard Bertsch** (Ruhr University) &
** Mark-Jan Nederhof** (Groningen University)

We recall the notion of regular closure of classes of
languages. We present two important results.
The first one 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 non-trivial result, since this closure contains
many inherently ambiguous languages.

The second one 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.

PDF version (9 pages, 200k)