Science Fair Project Encyclopedia
Prefix grammar
In computer science, a prefix grammar is a grammar, akin to the formal grammars, where strings are built up from a set of base strings by continually replacing prefixes. The prefix grammars describe exactly all regular languages.
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 productions of the form u → v where u and v are strings over Σ
Each production u → v can only be applied to a string of the form uw.
Example
One simple prefix grammar can be defined by
- Σ = {0, 1}
- S = {01, 10}
- P = {0 → 010, 10 → 100}
which describes the language defined by the regular expression
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details