Prefixgrammatica

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 $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 $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

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

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

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