40
$\begingroup$

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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
33
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 for the reference for the fact that all deterministic CFLs are not inherently ambiguous. In fact, that answers the other question as well: since there is an inherently ambiguous language, and it's not deterministic, it must be nondeterministic (notice that my definition of nondeterministic CFL isn't standard, since it excludes deterministic CFLs; that's my fault for misusing terminology). In any event, you have given an example for question (2), and shown that question (1) is an impossibility. I'll wait and see if somebody elaborates more, but will otherwise accept this as correct. Thanks! $\endgroup$
    – Patrick87
    Commented Mar 7, 2012 at 21:53
0
$\begingroup$

reading wikipedia & the answer & your comment on it, re (Q2) to state outright, all inherently ambiguous CFLs must be nondeterministic under the std defn (incl your own example!). ran across this ref

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.