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

*→*is a binary relation on the strings of Σ.

_{G}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