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 verschillende manieren kan worden gegenereerd. Dit houdt in dat er meer 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 bestaat er ook een equivalente eenduidige grammatica, dat wil zeggen een eenduidige grammatica die dezelfde taal genereert. Er bestaan echter ook contextvrije talen die alleen door ambigue grammatica's worden gegenereerd. Zulke talen worden inherent ambigu genoemd. Een voorbeeld van een inherent ambigue taal is $\{a^i{b}^j{c}^k\mid i=j\text{ of }j=k\}$.

Voorbeeld

De volgende contextvrije grammatica is ambigu aangezien er verschillende manieren bestaan om de zin $aaa$ te genereren:

$S\to aSa$

$S\to SS$

$S\to a$

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

$S\Rightarrow aSa\Rightarrow aaa$

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