Re: Decidability of Deterministic Context-Free Languages

On Jun 2, 5:55 pm, Matthias-Christian Ott <o...@mirix.org> wrote:
> 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.


Okay. Then another way of stating my original point is that it
depends when you "fix" the value of k. For any given k, the
deterministic nature of a grammar is trivially decidable. As you
said, just try to construct a LR(k) parse table.


However, if you let the value of k "free," you have a harder problem:
deciding whether a LR(k) parser exists for _any_ k. This is only semi-
decidable. I.e you can always be sure of a "yes" if that's the
answer. Just try to build a parser for k = 0,1,2, ... until you are
successful. On the other hand if the answer is "no," you can never be
sure. E.g. trying k=0,1,2,... you'll never be certain the next value
isn't the one that's successful. (Hence the old saw that's it's hard
to prove a negative.)


Semi-decidable is also undecidable, so there is no contradiction.

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