Re: Decidability of Deterministic Context-Free Languages

On Tue, Jun 01, 2010 at 07:29:57PM -0700, Gene wrote:
> On Jun 1, 5:47 pm, Matthias-Christian Ott <o...@mirix.org> wrote:
> > Hi,
> >
> > it is generally not decidable whether a context-free language is
> > deterministic. That means it is not decidable whether a grammar is an
> > LR(k) grammar.
>
> The last sentence here is problematic. This actually means that if you
> have a non-LR(k) grammar for a language (which after all is just a set
> of strings), the question of whether a LR(k) grammar exists for the
> same language is undecidable. As you imply later in your note, if you
> already have a LR(k) grammar, then you have a trivially decidable
> instance, but the general problem remains unsolvable.


No, I meant it is undecidable whether an abitrary context-free grammar
is deterministic. Several sources claim that LR(k) parsers and DPDA
both (only) recognize deterministic context-free languages.


However, I might have been a bit to careless about distinguishing
grammars from languages.


If you have context-free grammar you can contstruct a PDA from it and
determine whether it is detmerministic or not. So you can decide with
a context-free grammar either with a LR(k) parser or PDA whether it
is deterministic or not.


And as you said, this is trivial if you think about it a bit
longer. The hard thing (which is undecidable) is, given a context-free
language, to say if it exist a deterministic context-free grammar for
it. You can probably automatically infer a context-free grammar, but it
seems that you can't be sure that no deterministic context-free grammar
exists for it (probably this is proven for grammatical inference).


Regards,
Matthias-Christian

Return to the comp.compilers page.
Search the comp.compilers archives again.