Re: Decidability of Deterministic Context-Free Languages

On Wed, 2 Jun 2010 23:55:07 +0200, Matthias-Christian Ott
<ott@mirix.org> wrote:
>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.


This is definitely not true - it is trivially easy to produce a parser
that accepts any random string. However a non-deterministic language
is essentially useless for communication because most of the space is
meaningless. Grammatic rules exist to limit non-determinism so that
the accepted sub-language is (more) predictable and conveys more
meaning.


This is true even of context sensitive human 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.


Not exactly. You can decide whether the grammar represents a language
that can be parsed unambiguously with a given (k), but deciding that
the language is deterministic is a different matter. Ambiguity for a
given (k) does not mean the language is non-deterministic - it may
only mean that more look-ahead is required.




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


It's not really "undecidable" in the theoretical sense - but it is
"NP" hard which means getting an answer may require infinite time or
resources to compute.


In theory all you need to do generate a test language from the grammar
and compare it for equality with the original language. Generating
any particular string takes polynomic time, so generating the entire
possible language also takes (larger) polynomic time. Testing each
string also takes polynomic time, so comparing the languages is also
polynomic. But being polynomic does not exclude very large or
infinite terms, so in practice it is impractically hard to test any
but very simple grammars.


The reverse - inputting all strings from the language and verifying
that a parser recognizes them - does not work. The grammar used to
create the parser could specify a superset of the language, so you'd
also need to verify that all strings not in the language are rejected.




George

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