Editing 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 (computer science)|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 [[prefix (computer science)|prefixes]] are rewritten. The prefix grammars describe exactly all [[regular language]]s.<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 [[n-tuple|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]]