Ambigue grammatica

In de informatica wordt een contextvrije grammatica een ambigue grammatica genoemd als een bepaalde string (in deze context ook woord of zin genoemd) op meerdere manieren gegenereerd kan worden; dit houdt in dat er meerdere syntaxisbomen bestaan voor die string. Omdat een syntaxisboom vaak een-op-een samenhangt met de interpretatie van een zin, is het in de praktijk meestal ongewenst dat een grammatica ambigu is.

Een contextvrije grammatica is eenduidig als ze niet ambigu is. Bij veel ambigue grammatica's is het het geval, dat er ook een equivalent eenduidige grammatica bestaat, dat wil zeggen een eenduidige grammatica die dezelfde taal genereert. Er bestaan echter contextvrije talen die slechts door ambigue grammatica's gegenereerd worden; zulke talen worden inherent ambigu genoemd. Een voorbeeld van een inherent ambigue taal is $\{a^{i}b^{j}c^{k}\mid i=j{\mbox{ of }}j=k\}$.

Voorbeeld

De volgende context-vrije grammatica is ambigue aangezien er meerdere manieren bestaan om de zin $aaa$ te genereren:

$S\rightarrow aSa$

$S\rightarrow SS$

$S\rightarrow a$

De zin $aaa$ kan op onder andere de volgende manieren gegenereerd worden:

$S\Rightarrow aSa\Rightarrow aaa$

$S\Rightarrow SS\Rightarrow aS\Rightarrow aSS\Rightarrow aaS\Rightarrow aaa$

Er zijn nog enkele andere manieren om de zin af te leiden aangezien men bij het gebruik van de productieregel $S\rightarrow SS$ de keuze heeft of men eerst het linker of het rechter niet-terminale symbool verder uitwerkt.