Greibach-normaalvorm: verschil tussen versies
k Robot: Verplaatsing van 13 interwikilinks. Deze staan nu op Wikidata onder d:q1499325 |
k Fix link naar contextvrije talen |
||
Regel 1: | Regel 1: | ||
De '''Greibach normaalvorm''' is een begrip uit de [[theoretische informatica]], dat in het verband van [[contextvrije talen]] van belang is. Zij is vernoemd naar de informatica [[Sheila A. Greibach]] uit de [[Verenigde Staten]] en beschrijft een normaalvorm van een [[contextvrije grammatica]], dus een deelverzameling van de contextvrije grammatica's die niet minder uitdrukkingskracht heeft dan de verzameling van algemene contextvrije grammatica's. De opvallendste eigenschap van de Greibach normaalvorm is, dat bij elke productieregel precies één terminaal symbool voorkomt. Daarmee is zij de natuurlijke tussenstap bij de omzetting van een contextvrije grammatica naar een equivalente niet-deterministische [[Stapelautomaat|pushdown automaat (PDA)]] zonder <math>\epsilon</math>-producties. |
De '''Greibach normaalvorm''' is een begrip uit de [[theoretische informatica]], dat in het verband van [[contextvrije taal|contextvrije talen]] van belang is. Zij is vernoemd naar de informatica [[Sheila A. Greibach]] uit de [[Verenigde Staten]] en beschrijft een normaalvorm van een [[contextvrije grammatica]], dus een deelverzameling van de contextvrije grammatica's die niet minder uitdrukkingskracht heeft dan de verzameling van algemene contextvrije grammatica's. De opvallendste eigenschap van de Greibach normaalvorm is, dat bij elke productieregel precies één terminaal symbool voorkomt. Daarmee is zij de natuurlijke tussenstap bij de omzetting van een contextvrije grammatica naar een equivalente niet-deterministische [[Stapelautomaat|pushdown automaat (PDA)]] zonder <math>\epsilon</math>-producties. |
||
Een ander normaalvorm voor contextvrije grammatica's is de [[Chomsky-normaalvorm]]. |
Een ander normaalvorm voor contextvrije grammatica's is de [[Chomsky-normaalvorm]]. |
Versie van 12 jun 2015 11:56
De Greibach normaalvorm is een begrip uit de theoretische informatica, dat in het verband van contextvrije talen van belang is. Zij is vernoemd naar de informatica Sheila A. Greibach uit de Verenigde Staten en beschrijft een normaalvorm van een contextvrije grammatica, dus een deelverzameling van de contextvrije grammatica's die niet minder uitdrukkingskracht heeft dan de verzameling van algemene contextvrije grammatica's. De opvallendste eigenschap van de Greibach normaalvorm is, dat bij elke productieregel precies één terminaal symbool voorkomt. Daarmee is zij de natuurlijke tussenstap bij de omzetting van een contextvrije grammatica naar een equivalente niet-deterministische pushdown automaat (PDA) zonder -producties.
Een ander normaalvorm voor contextvrije grammatica's is de Chomsky-normaalvorm.
Formele Definitie
Zij een formele grammatica van een contextvrije taal (vgl. Chomskyhiërarchie), zodat dus . Zij de lege string .
, met , is in Greibach normalvorm (afgekort GNF), als alle productieregels uit de met aannemen, waarbij (niet-terminale symbolen) en (terminale symbolen). Als we nemen zijn reguliere grammatica's een speciaal geval van een contextvrije grammatica in Greibach normaalvorm.
Voor alle met is er een in Greibach normaalvorm met .