Editing Prefix grammar (section)

==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>}}.