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,, where
For strings x, y, we write x →G y 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