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. Formal definition. A prefix grammar "G" is a 3-tuple, (Σ, "S", "P"), where For strings "x", "y", we write "x" → "y" (and say: "G" can derive  y from "x" in one step) if there are strings "u, v, w" such that , and "v" → "w" is in "P". Note that is a binary relation on the strings of Σ. The "language" of "G", denoted , 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 . Example. The prefix grammar describes the language defined by the regular expression