Prefix grammar

In computer science, 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.

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 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 "→_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 "→_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^*$

Properties

The prefix grammars describe exactly all regular languages. [ [http://portal.acm.org/citation.cfm?id=185820 M. Frazier and C. D. Page. Prefix grammars: An alternative characterization of the regular languages. Information Processing Letters, 51(2):67–71, 1994.] ]

References

ee also

* Regular grammar
* Simple grammar