Re: Decidability of Deterministic Context-Free Languages

Gene <gene.ressler@gmail.com>
Tue, 1 Jun 2010 19:29:57 -0700 (PDT)

          From comp.compilers

Related articles
Decidability of Deterministic Context-Free Languages ott@mirix.org (Matthias-Christian Ott) (2010-06-01)
Re: Decidability of Deterministic Context-Free Languages gneuner2@comcast.net (George Neuner) (2010-06-01)
Re: Decidability of Deterministic Context-Free Languages gene.ressler@gmail.com (Gene) (2010-06-01)
Re: Decidability of Deterministic Context-Free Languages torbenm@diku.dk (2010-06-02)
Re: Decidability of Deterministic Context-Free Languages ott@mirix.org (Matthias-Christian Ott) (2010-06-02)
Re: Decidability of Deterministic Context-Free Languages gene.ressler@gmail.com (Gene) (2010-06-06)
Re: Decidability of Deterministic Context-Free Languages gneuner2@comcast.net (George Neuner) (2010-06-07)
| List of all articles for this month |

From: Gene <gene.ressler@gmail.com>
Newsgroups: comp.compilers
Date: Tue, 1 Jun 2010 19:29:57 -0700 (PDT)
Organization: Compilers Central
References: 10-06-003
Keywords: parse, theory
Posted-Date: 02 Jun 2010 09:01:33 EDT

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.



Post a followup to this message

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