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?

  • 5
    $\begingroup$ 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$. $\endgroup$
    – Sylvain
    May 24, 2014 at 14:27
  • $\begingroup$ @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? $\endgroup$ May 24, 2014 at 21:53
  • $\begingroup$ 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)". $\endgroup$
    – Sylvain
    May 25, 2014 at 8:33
  • $\begingroup$ I hadn't looked at the wikipedia page. 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. $\endgroup$
    – Sylvain
    May 25, 2014 at 8:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – Sylvain
    May 25, 2014 at 22:13

1 Answer 1


See this related Wikipedia link:


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.


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.