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 .

Voorbeeld bewerken

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

 
 
 

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