Are there inherently ambiguous and deterministic context-free languages?

Problem Detail: 

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: $$\{a^{n}b^{n} \in \{a, b\}^{*} | n \ge 0\}$$ An example of a nondeterministic, unambiguous language is the language: $$\{w \in \{a, b\}^{*} | w = w^{R}\}$$

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 = \{a^{n}b^{m}c^{m}d^{n} \in \{a, b, c, d\}^{*} | n, m \ge 0\} \cup \{a^{n}b^{n}c^{m}d^{m} \in \{a, b, c, d\}^{*} | n, m \ge 0\}$$

Now for the questions:

1. Is it known whether there exists a deterministic, inherently ambiguous context-free language? If so, is there an (easy) example?
2. 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).

Asked By : Patrick87

Answered By : Alex ten Brink

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/109