Prefixgrammatica

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de theoretische informatica is een prefixgrammatica een formele grammatica waarin de productieregels alleen aan het begin van het her te schrijven woord mogen worden toegepast; er worden dus alleen prefixen herschreven. Prefixgrammatica's genereren precies de klasse van reguliere talen.

Definitie[bewerken]

Een prefixgrammatica is een structuur , waarbij

  • een eindige verzameling symbolen is, een alfabet genoemd;
  • een eindige verzameling basiswoorden is; en
  • een eindige verzameling productieregels van de vorm is, waarbij en woorden zijn.

Een woord kan tot een woord herschreven worden, als er een regel en een woord bestaan, zodat en . De taal van een prefixgrammatica bestaat uit alle basiswoorden van en uit alle woorden die in een of meer herschrijfstappen uit een van de basiswoorden kunnen worden afgeleid.

Prefixgrammatica's verschillen op verschillende punten van normale grammatica's:

  • In prefixgrammatica's zijn de symbolen niet onderverdeeld in terminaalsymbolen en variabelen. Dat betekent dat alle woorden die door een prefixgrammatica kunnen worden afgeleid tot de taal van de grammatica behoren, en niet alleen die woorden die alleen uit terminaalsymbolen bestaan.
  • In normale grammatica's wordt meestal verboden dat de linker kant van een regel het lege woord is. Bij prefixgrammatica's is dit toegestaan.
  • In prefixgrammatica's mag alleen aan het begin van het woord worden herschreven. Bij normale grammatica's mag een regel op elke plek in het woord worden toegepast.

De taal van een prefixgrammatica[bewerken]

De taal van een prefixgrammatica is altijd regulier. Andersom bestaat er voor elke reguliere taal een prefixgrammatica die haar genereert. Prefixgrammatica's genereren dus precies de klasse van reguliere talen.

Aangezien de stapel van een stapelautomaat in feite een woord is dat slechts aan één kant veranderd kan worden, volgt uit dit resultaat dat de taal van mogelijke stapelinhouden van een stapelautomaat regulier is, hoewel stapelautomaten contextvrije talen kunnen accepteren.

Voorbeeld[bewerken]

Laat de prefixgrammatica gegeven zijn, met:

Deze prefixgrammatica genereert dezelfde taal als de reguliere expressie . Het woord kan bijvoorbeeld als volgt worden gegenereerd:

Bronnen[bewerken]

  • Michael Frazier, C. David Page Jr. Prefix grammars: An alternative characterization of the regular languages. Information Processing Letters 51, 1994.