ambiguous grammar
Let $G=(\mathrm{\Sigma},N,P,\sigma )$ be a contextfree grammar, and $L(G)$ the language^{} generated by it. Since every word in $L(G)$ has at least one leftmost derivation, let us only consider leftmost derivations of words.
Definition. $G$ is said to be unambiguous if every word in $L(G)$ has exactly one leftmost derivation. Otherwise, $G$ is said to be ambiguous.
For an example of an ambiguous grammar, let $G$ be the grammar^{} consisting of $a,b$ as terminal symbols, $\sigma ,X$ as nonterminal symbols, and $\sigma \to a$, $\sigma \to ab\sigma b$, $\sigma \to aXb$, and $X\to b\sigma $ as productions. By definition, $G$ is contextfree. Then the word $abab$ has

•
$\sigma \to ab\sigma b\to abab$, and

•
$\sigma \to aXb\to ab\sigma b\to abab$,
two leftmost derivations (corresponding to the following derivation trees).
Hence $G$ is ambiguous.
An example of an unambiguous grammar can be found when we convert the language formation rules of the classical propositional logic^{} to a formal grammar. This grammar is contextfree. By unique readability of wellformed formulas (words in this language), we conclude that the grammar is unambiguous.
Remarks.

•
A grammar $G$ is unambiguous iff every word in $L(G)$ corresponds to a uniuqe derivation tree, since every derivation tree corresponds to a unique leftmost derivation.

•
Deciding whether a contextfree grammar is ambiguous is undecidable unless it has only one terminal symbol.
The concept^{} of ambiguity can be carried over to contextfree languages. Since every contextfree language can be generated by many contextfree grammars, some of which may be ambiguous, while others may not be, there are potentially three classes of contextfree languages:

1.
those that can only be generated by unambiguous grammars,

2.
those that can be generated by ambiguous, as well as unambiguous grammars,

3.
those that can only be generated by ambiguous grammars.
However, the first class is an empty set^{}: every contextfree language can be generated by an ambiguous grammar. Suppose $G$ is a contextfree grammar generating the language $L$. If $G$ contains the production $\sigma \to \sigma $, then $G$ is ambiguous, for any leftmost derivation $\sigma \stackrel{*}{\to}w$ of a word $w$ can be lengthened to a leftmost derivation $\sigma \to \sigma \stackrel{*}{\to}w$. If $G$ does not contain $\sigma \to \sigma $, the grammar ${G}^{\prime}$ obtained by adding the production $\sigma \to \sigma $ to $G$ generates $L$ as well, and is ambiguous as we have just shown.
The other two classes are formally defined as follows:
Definition. A contextfree language is unambiguous if it can be generated by an unambiguous grammar. Otherwise, it is said to be inherently ambiguous.
It can be shown that any regular language is unambiguous, and so is any deterministic contextfree language (a language generated by a deterministic pushdown automaton). In addition, the intersection^{} as well as the difference of a unambiguous contextfree language with a regular^{} langauge is unambiguous and contextfree.
Nevertheless, inherently ambiguous languages do exist. Several explicit examples can be found in Ginsburg, one of which is the union of two contextfree languages $\{{a}^{i}{b}^{i}{c}^{j}\mid i,j\ge 1\}$ and $\{{a}^{i}{b}^{j}{c}^{j}\mid i,j\ge 1\}$.
Remark. It is undecidable whether a contextfree language over at least two symbols is inherently ambiguous.
References
 1 S. Ginsburg, The Mathematical Theory of ContextFree Languages, McGrawHill, New York (1966).
 2 D. C. Kozen, Automata and Computability, Springer, New York (1997).
Title  ambiguous grammar 

Canonical name  AmbiguousGrammar 
Date of creation  20130322 18:54:57 
Last modified on  20130322 18:54:57 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  14 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q42 
Classification  msc 68Q45 
Related topic  DeterministicPushdownAutomaton 
Defines  ambiguous 
Defines  inherently ambiguous 
Defines  unambiguous 