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.<ref>[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.]</ref>
==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'' →<sub>''G''</sub> ''y'' (and say: ''G'' can derive ''y'' from ''x'' in one step) if there are strings ''u, v, w'' such that {{tmath|1=x = vu, y = wu}}, and ''v'' → ''w'' is in ''P''. Note that {{math|→<sub>''G''</sub>}} is a binary relation on the strings of Σ.
The ''language'' of ''G'', denoted {{tmath|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 {{math|→<sub>''G''</sub>}}.
==Example== The prefix grammar *Σ = {0, 1} *''S'' = {01, 10} *''P'' = {0 → 010, 10 → 100} describes the language defined by the regular expression :<math> 01(01)^* \cup 100^* </math>
==See also == * Regular grammar
==References== {{reflist}}
Category:Formal languages