Wikipedia:
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 production rules 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
Properties
Prefix grammars generate languages that are prefix closed.
See also
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
