Ambiguous grammar

If there are several right-hand or left-hand derivatives for a word in relation to a formal grammar, or if there are two different right-hand or two different left-hand derivative trees for a word in the grammar that are not isomorphic to one another, then this grammar is called ambiguous .

example

Given the language, the grammar with and the following rule set : ${\displaystyle L=\left\{aa\right\}}$ ${\displaystyle G=\left(\{S,A,B\},\{a\},P,S\right)}$ ${\displaystyle L\left(G\right)=L}$ ${\displaystyle P}$

${\displaystyle S\rightarrow AA}$

${\displaystyle S\rightarrow BB}$

${\displaystyle A\rightarrow a}$

${\displaystyle B\rightarrow a}$

The grammar is ambiguous because two different left derivatives can be used to generate the word . ${\displaystyle G}$ ${\displaystyle aa}$

${\displaystyle S\Rightarrow _{G}AA\Rightarrow _{G}aA\Rightarrow _{G}aa}$

${\displaystyle S\Rightarrow _{G}BB\Rightarrow _{G}aB\Rightarrow _{G}aa}$

${\displaystyle \Rightarrow _{G}}$symbolizes the transition relation .

See also

• Derivation (computer science)
• Inherently ambiguous language