<p>See this related Wikipedia link:</p>

<p><a href="http://en.wikipedia.org/wiki/Unambiguous_grammar#Recognizing_ambiguous_grammars" rel="nofollow">http://en.wikipedia.org/wiki/Unambiguous_grammar#Recognizing_ambiguous_grammars</a></p>

<blockquote>
  <p>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.
  <strong>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]</strong> 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.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>The definition of grammar <strong>ambiguity</strong> addresses the actual syntactical <strong>structure of the grammar</strong> 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.</p>

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

CC BY-SA 3.0
2014-05-25T12:41:08.397Z
2014-05-25T12:41:08.397Z
sweetname
<p>Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars.  <a href="http://en.wikipedia.org/wiki/Deterministic_context-free_grammar" rel="noreferrer">According to</a> <a href="http://en.wikipedia.org/wiki/Unambiguous_grammar" rel="noreferrer">Wikipedia however</a>, this is false:</p>

<blockquote>
  <p>there are non-deterministic unambiguous CFGs</p>
</blockquote>

<p>What is the difference between ambiguity and determinism in grammars?  What is an example of a grammar that is non-deterministic but unambiguous?</p>

CC BY-SA 3.0
2014-05-24T14:27:21.647Z
First, there is no such thing as a ''deterministic _grammar_''; however, a context-free _language_ $L$ is deterministic if there exists a deterministic pushdown automaton that recognizes it.  The even length palindromes over a binary alphabet form a non-deterministic language $\{ww^R\mid w\in\{a,b\}^\ast\}$ (where $w^R$ denotes the reversal of word $w$), which is unambiguous: there exists an unambiguous _grammar_ for it, e.g. $S\to a\,S\,a\mid b\,S\,b\mid\varepsilon$.
Sylvain
CC BY-SA 3.0
2014-05-24T21:53:24.887Z
@Sylvain just to make sure I understand you -- the Wikipedia article is wrong when it says that "In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars"?  In that case, maybe I should just delete the OP?
Matt Fenwick
CC BY-SA 3.0
2014-05-25T08:33:49.387Z
I think it's an improper use: languages or automata can be deterministic, not grammars.  The correct statement would be "In formal grammar theory, the deterministic context-free languages (DCFL) are a proper subset of the context-free languages (CFL)".
Sylvain
CC BY-SA 3.0
2014-05-25T08:38:51.313Z
I hadn't looked at the [wikipedia page](http://en.wikipedia.org/wiki/Deterministic_context-free_grammar).  They define deterministic CFGs as those for which there exists a DPDA with the same language.  It's a dangerous definition, because it doesn't tell you _how_ to construct this DPDA.  A paragraph later they write nonsense: "DCFGs are of great practical interest, as they can be parsed in linear time and in fact a parser can be automatically generated from the grammar by a parser generator", altough it is *undecidable*, given a CFG, whether its language is a DCFL.
Sylvain
CC BY-SA 3.0
2014-05-25T13:53:29.910Z
@Sylvain I know the ambiguity problem is undecidable but I thought it was decidable whether a given CFG is deterministic. There is a description of a "DK-test" in Sipser's introductory book (3rd edition) that a CFG passes iff it is deterministic.
sjmc
CC BY-SA 3.0
2014-05-25T22:13:35.540Z
@sjmc: What Sipser calls DCFG is the class of LR(0) grammars (p. 152 of Sipster's _Introduction to the Theory of Computation_ 3rd Edition).  For such grammars, and more generally LR($k$) grammars for some fixed $k$, you have an effective DPDA construction.
Sylvain
<fl.formal-languages><grammars><nondeterminism>
What are the relationship and difference between ambiguous grammars and non-deterministic ones?
Matt Fenwick
# What are the relationship and difference between ambiguous grammars and non-deterministic ones?

(Asked by: username_0 on 2014-05-24)

Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars. [According to](http://en.wikipedia.org/wiki/Deterministic_context-free_grammar) [Wikipedia however](http://en.wikipedia.org/wiki/Unambiguous_grammar), 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?

**Tags:** fl.formal-languages, grammars, nondeterminism

> **Comments:**
> **username_1**: First, there is no such thing as a ''deterministic _grammar_''; however, a context-free _language_ $L$ is deterministic if there exists a deterministic pushdown automaton that recognizes it.  The even length palindromes over a binary alphabet form a non-deterministic language $\{ww^R\mid w\in\{a,b\}^\ast\}$ (where $w^R$ denotes the reversal of word $w$), which is unambiguous: there exists an unambiguous _grammar_ for it, e.g. $S\to a\,S\,a\mid b\,S\,b\mid\varepsilon$.  
> **username_0**: @username_1 just to make sure I understand you -- the Wikipedia article is wrong when it says that "In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars"?  In that case, maybe I should just delete the OP?  
> **username_1**: I think it's an improper use: languages or automata can be deterministic, not grammars.  The correct statement would be "In formal grammar theory, the deterministic context-free languages (DCFL) are a proper subset of the context-free languages (CFL)".  
> **username_1**: I hadn't looked at the [wikipedia page](http://en.wikipedia.org/wiki/Deterministic_context-free_grammar).  They define deterministic CFGs as those for which there exists a DPDA with the same language.  It's a dangerous definition, because it doesn't tell you _how_ to construct this DPDA.  A paragraph later they write nonsense: "DCFGs are of great practical interest, as they can be parsed in linear time and in fact a parser can be automatically generated from the grammar by a parser generator", altough it is *undecidable*, given a CFG, whether its language is a DCFL.  
> **username_2**: @username_1 I know the ambiguity problem is undecidable but I thought it was decidable whether a given CFG is deterministic. There is a description of a "DK-test" in Sipser's introductory book (3rd edition) that a CFG passes iff it is deterministic.  
> **username_1**: @username_2: What Sipser calls DCFG is the class of LR(0) grammars (p. 152 of Sipster's _Introduction to the Theory of Computation_ 3rd Edition).  For such grammars, and more generally LR($k$) grammars for some fixed $k$, you have an effective DPDA construction.  

---

## 1 answers

### Answer by username_3 on 2014-05-25. Score: 2

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.


---

