title: Prefixgrammatica
text: 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 
  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 
  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 
  Laat de prefixgrammatica  gegeven zijn, met:
   
   
   
  Deze prefixgrammatica genereert dezelfde taal als de reguliere expressie . Het woord  kan bijvoorbeeld als volgt worden gegenereerd:
  
  Bronnen 
   Michael Frazier, C. David Page Jr. Prefix grammars: An alternative characterization of the regular languages. Information Processing Letters 51, 1994.
  
  Formele taal