Wed, 2 Jun 2010 23:55:07 +0200

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) |

From: | Matthias-Christian Ott <ott@mirix.org> |

Newsgroups: | comp.compilers |

Date: | Wed, 2 Jun 2010 23:55:07 +0200 |

Organization: | Compilers Central |

References: | 10-06-003 10-06-005 |

Keywords: | parse, theory |

Posted-Date: | 03 Jun 2010 15:08:37 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.