Prefix grammar

In theoretical computer science and formal language theory, a prefix grammar is a type of string rewriting system, consisting of a set of string rewriting rules, and similar to a formal grammar or a semi-Thue system. What is specific about prefix grammars is not the shape of their rules, but the way in which they are applied: only prefixes are rewritten. The prefix grammars describe exactly all regular languages.^[1]

Formal definition

A prefix grammar G is a 3-tuple, (Σ, S, P), where

Σ is a finite alphabet
S is a finite set of base strings over Σ
P is a finite set of production rules of the form u → v where u and v are strings over Σ

For strings x, y, we write x →_G y (and say: G can derive y from x in one step) if there are strings u, v, w such that ⁠ $x=vu,y=wu$ ⁠, and v → w is in P. Note that $\to G$ is a binary relation on the strings of Σ.

The language of G, denoted ⁠ $L(G)$ ⁠, is the set of strings derivable from S in zero or more steps: formally, the set of strings w such that for some s in S, s R w, where R is the transitive closure of $\to G$ .

Example

The prefix grammar

Σ = {0, 1}
S = {01, 10}
P = {0 → 010, 10 → 100}

describes the language defined by the regular expression

01(01)^{*}\cup 100^{*}

References

^ M. Frazier and C. D. Page. Prefix grammars: An alternative characterization of the regular languages. Information Processing Letters, 51(2):67–71, 1994.

[1] M. Frazier and C. D. Page. Prefix grammars: An alternative characterization of the regular languages. Information Processing Letters, 51(2):67–71, 1994.

[1]

Formal definition

Example

See also

References