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