What are the relationship and difference between ambiguous grammars and non-deterministic ones? Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars.  According to Wikipedia however, this is false:


  there are non-deterministic unambiguous CFGs


What is the difference between ambiguity and determinism in grammars?  What is an example of a grammar that is non-deterministic but unambiguous?
See this related Wikipedia link:

http://en.wikipedia.org/wiki/Unambiguous_grammar#Recognizing_ambiguous_grammars


  The efficiency of context-free grammar parsing is determined by the
  automaton that accepts it. Deterministic context-free grammars are
  accepted by deterministic pushdown automata and can be parsed in
  linear time, for example by the LR parser.[3] This is a subset of the
  context-free grammars which are accepted by the pushdown automaton and
  can be parsed in polynomial time, for example by the CYK algorithm.
  Unambiguous context-free grammars can be nondeterministic. For example, the language of even-length palindromes on the alphabet of 0
  and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An
  arbitrary string of this language cannot be parsed without reading all
  its letters first which means that a pushdown automaton has to try
  alternative state transitions to accommodate for the different
  possible lengths of a semi-parsed string.[4] Nevertheless, removing
  grammar ambiguity may produce a deterministic context-free grammar and
  thus allow for more efficient parsing. Compiler generators such as
  YACC include features for resolving some kinds of ambiguity, such as
  by using the precedence and associativity constraints.


An ambiguous grammar may be defined as a grammar for which there exists more than one parse tree for some string belonging to the language it generates.

A deterministic grammar may be defined as a grammar for which there exists a deterministic machine model which is capable of recognizing the language it generates.

Assume Grammar 1 generates the same language as Grammar 2.  Assume Grammar 1 is unambiguous and Grammar 2 is ambiguous.  If a deterministic machine model is capable of recognizing the language generated by Grammar 1, then it is also capable of recognizing the language generated by Grammar 2 (by the assumption that they both generate the same language).  Clearly, both are deterministic grammars and yet they differ on the question of ambiguity.

The definition of grammar ambiguity addresses the actual syntactical structure of the grammar and its relation to parsing, NOT whether an ambiguous grammar could be structured differently so as to generate the same language and yet remove ambiguity.

The definition of grammar determinism, however, is not related to the structure of a grammar but rather to the properties of the language it generates regarding recognition by an appropriate deterministic machine model.