How is non-ambuiguity different from determinism?

I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an example more then the most elaborate explanation! If possible.

My primary source of confusion is from not being able to tell how this property of a grammar is different from (non-)ambiguity.

The closest I got to finding what it means is this quote from the paper by D. Knuth On the Translation of Languages from Left to Right:


Ginsburg and Greibach (1965) have defined the notion of a
deterministic language; we show in Section V that these are precisely
the languages for which there exists an L R ( k ) grammar

which becomes circular as soon you get to the Section V, because there it says that what LR(k) parser can parse is the deterministic language...

Below is an example that I could find to help me understand what "ambigous" means, please take a look:

onewartwoearewe

Which can be parsed as one war two ear ewe or o new art woe are we - if a grammar allows that (say it has all the words I just listed).

What would I need to do to make this example language (non-)deterministic? (I could, for example, remove the word o from the grammar, to make the grammar not ambiguous).

Is the above language deterministic?

PS. The example is from the book Godel, Esher, Bach: Eternal Golden Braid.

Let's say, we define the grammar for the example language like so:

S -> A 'we' | A 'ewe'
A -> B | BA
B -> 'o' | 'new' | 'art' | 'woe' | 'are' | 'one' | 'war' | 'two' | 'ear'

By the argument about having to parse the whole string, does this grammar make the language non-deterministic?

```
let explode s =
let rec exp i l =
if i true
| 'e' :: 'w' :: 'e' :: [] -> true
| 'o' :: x -> woe_parser x
| 'n' :: 'e' :: 'w' :: x -> woe_parser x
| 'a' :: 'r' :: 't' :: x -> woe_parser x
| 'w' :: 'o' :: 'e' :: x -> woe_parser x
| 'a' :: 'r' :: 'e' :: x ->

A PDA is deterministic, hence a DPDA, iff for every reachable configuration of the automaton, there is at most one transition (i.e., at most one new configuration possible). If you have a PDA which can reach some configuration for which two or more unique transitions may be possible, you do not have a DPDA.

Example:

Consider the following family of PDAs with $Q = \{q_0, q_1\}$, $\Sigma = \Gamma = \{a, b\}$, $A = q_0$ and $\delta$ given by the following table:

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
...

These are nondeterministic PDAs because the initial configuration - q_0, Z0 - is reachable, and there are two valid transitions leading away from it if the input symbol is a. Anytime this PDA starts trying to process a string that begins with an a, there's a choice. Choice means nondeterministic.

Consider, instead, the following transition table:

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
q1   a    a    q0   aa
q1   a    b    q0   ab
q1   a    b    q2   aa
q2   b    a    q0   ba
q2   b    b    q0   bb
q2   b    a    q1   bb

You might be tempted to say this PDA is nondeterministic; after all, there are two valid transitions away from the configuration q1, b(a+b), for instance. However, since this configuration is not reachable by any path through the automaton, it doesn't count. The only reachable configurations are a subset of q_0, (a+b)Z0, q1, a(a+b)Z0, and q2, b(a+b)Z0, and for each of these configurations, at most one transition is defined.

A CFL is deterministic iff it is the language of some DPDA.

A CFG is unambiguous if every string has at most one valid derivation according to the CFG. Otherwise, the grammar is ambiguous. If you have a CFG and you can produce two different derivation trees for some string, you have an ambiguous grammar.

A CFL is inherently ambiguous iff it is not the language of any unambiguous CFG.

Note the following:

• A deterministic CFL must be the language of some DPDA.

• Every CFL is the language of infinitely many nondeterministic PDAs.

• An inherently ambiguous CFL is not the language of any unambiguous CFG.

• Every CFL is the language of infinitely many ambiguous CFGs.

• An inherently ambiguous CFL cannot be deterministic.

• A nondeterministic CFL may or may not be inherently ambiguous.

StackExchange Computer Science Q#14583, answer score: 9