How is non-ambuiguity different from determinism?

Problem Detail: 

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 < 0 then l else exp (i - 1) (s.[i] :: l) in   exp (String.length s - 1) [];;  let rec woe_parser s =   match s with   | 'w' :: 'e' :: [] -> 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 -> woe_parser x   (* this line will trigger an error, because it creates       ambiguous grammar *)   | 'o' :: 'n' :: 'e' :: x -> woe_parser x   | 'w' :: 'a' :: 'r' :: x -> woe_parser x   | 't' :: 'w' :: 'o' :: x -> woe_parser x   | 'e' :: 'a' :: 'r' :: x -> woe_parser x   | _ -> false;;  woe_parser (explode "onewartwoearewe");; - : bool = true 

---

| Label   | Pattern      | |---------+--------------| | rule-01 | S -> A 'we'  | | rule-02 | S -> A 'ewe' | | rule-03 | A -> B       | | rule-04 | A -> BA      | | rule-05 | B -> 'o'     | | rule-06 | B -> 'new'   | | rule-07 | B -> 'art'   | | rule-08 | B -> 'woe'   | | rule-09 | B -> 'are'   | | rule-10 | B -> 'one'   | | rule-11 | B -> 'war'   | | rule-12 | B -> 'two'   | | rule-13 | B -> 'ear'   | #+TBLFM: @2$1..@>$1='(format "rule-%02d" (1- @#));L  Generating =onewartwoearewe=  First way to generate:  | Input             | Rule    | Product           | |-------------------+---------+-------------------| | ''                | rule-01 | A'we'             | | A'we'             | rule-04 | BA'we'            | | BA'we'            | rule-05 | 'o'A'we'          | | 'o'A'we'          | rule-04 | 'o'BA'we'         | | 'o'BA'we'         | rule-06 | 'onew'A'we'       | | 'onew'A'we'       | rule-04 | 'onew'BA'we'      | | 'onew'BA'we'      | rule-07 | 'onewart'A'we'    | | 'onewart'A'we'    | rule-04 | 'onewart'BA'we'   | | 'onewart'BA'we'   | rule-08 | 'onewartwoe'A'we' | | 'onewartwoe'A'we' | rule-03 | 'onewartwoe'B'we' | | 'onewartwoe'B'we' | rule-09 | 'onewartwoearewe' | |-------------------+---------+-------------------| |                   |         | 'onewartwoearewe' |  Second way to generate:  | Input             | Rule    | Product           | |-------------------+---------+-------------------| | ''                | rule-02 | A'ewe'            | | A'ewe'            | rule-04 | BA'ewe'           | | BA'ewe'           | rule-10 | 'one'A'ewe'       | | 'one'A'ewe'       | rule-04 | 'one'BA'ewe'      | | 'one'BA'ewe'      | rule-11 | 'onewar'A'ewe'    | | 'onewar'A'ewe'    | rule-04 | 'onewar'BA'ewe'   | | 'onewar'BA'ewe'   | rule-12 | 'onewartwo'A'ewe' | | 'onewartwo'A'ewe' | rule-03 | 'onewartwo'B'ewe' | | 'onewartwo'B'ewe' | rule-13 | 'onewartwoearewe' | |-------------------+---------+-------------------| |                   |         | 'onewartwoearewe' | 

Asked By : wvxvw

Answered By : Patrick87

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.

Best Answer from StackOverflow

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