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 G = (\Sigma, S, P), waarbij

  • \Sigma een eindige verzameling symbolen is, een alfabet genoemd;
  • S een eindige verzameling basiswoorden is; en
  • P een eindige verzameling productieregels van de vorm \alpha\to\beta is, waarbij \alpha en \beta woorden zijn.

Een woord \gamma kan tot een woord \gamma' herschreven worden, als er een regel \alpha\to\beta\in P en een woord \omega bestaan, zodat \gamma=\alpha\omega en \gamma'=\beta\omega. De taal van L(G) van een prefixgrammatica G bestaat uit alle basiswoorden van G 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 L(G) 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 G=(\Sigma,S,P) gegeven zijn, met:

  • \Sigma=\{0,1\}
  • S = \{01\}
  • P = \{0 \to 001, 01 \to 011\}

Deze prefixgrammatica genereert dezelfde taal als de reguliere expressie 0(01)^*11^*. Het woord 0010111 kan bijvoorbeeld als volgt worden gegenereerd:

01 \Rightarrow 011 \Rightarrow 00111 \Rightarrow 0010111

Bronnen[bewerken]

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