Let us call a context-free language deterministic if and only if it can be accep

Question

Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.

Let us call a context-free language inherently ambiguous if and only if all context-free grammars which generate the language are ambiguous, and unambiguous otherwise.

An example of a deterministic, unambiguous language is the language:
{anbn?{a,b}?|n?0}
An example of a nondeterministic, unambiguous language is the language:
{w?{a,b}?|w=wR}

From Wikipedia, an example of an inherently ambiguous context-free language is the following union of context-free languages, which must also be context-free:
L={anbmcmdn?{a,b,c,d}?|n,m?0}?{anbncmdm?{a,b,c,d}?|n,m?0}

Now for the questions:

Is it known whether there exists a deterministic, inherently ambiguous context-free language? If so, is there an (easy) example?
Is it known whether there exists a nondeterministic, inherently ambiguous context-free language? If so, is there an (easy) example?

Clearly, since an inherently ambiguous context-free language exists (L is an example), the answer to one of these questions is easy, if it is known whether L is deterministic or nondeterministic. I also assume that it's true that if there's a deterministic one, there's bound to be a nondeterministic one as well... but I've been surprised before. References are appreciated, and apologies in advance if this is a well-known, celebrated result (in which case, I'm completely unaware of it).

Explanation / Answer

If a language L is deterministic, it is accepted by some deterministic push-down automaton, which in turn means there is some LR(1) grammar describing the language, and as every LR(1) grammar is unambiguous, this means that L cannot be inherently ambiguous. Knuth proved this in his paper in which he introduced LR(1) (On the Translation of Languages from Left to Right).

A language can be described by some context-free grammar if and only if it can be recognized by some nondeterministic automaton. As a special case of this, inherently ambiguous context-free grammars can be parsed by some nondeterministic automaton.

On a final note, any deterministic push-down automaton is also nondeterministic (this is the case for just about anything that can be nondeterministic, for a reasonable definition of nondeterminism).

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.