Prefix grammar
Encyclopedia
In computer science
, 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 language
s.
For strings x, y, we write x →G y (and say: G can derive y from x in one step) if there are strings u, v, w such that x = vu, y = wu, and v → w is in P. Note that →G is a binary relation
on the strings of Σ.
The language of G, denoted 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 →G.
describes the language defined by the regular expression
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a prefix grammar is a type of string rewriting system, consisting of a set of string
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
rewriting
Rewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. What is considered are rewriting systems...
rules, and similar to a formal grammar
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
or a semi-Thue system
Semi-Thue system
In theoretical computer science and mathematical logic a string rewriting system , historically called a semi-Thue system, is a rewriting system over strings from a alphabet...
. 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 language
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s.
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 Σ
For strings x, y, we write x →G y (and say: G can derive y from x in one step) if there are strings u, v, w such that x = vu, y = wu, and v → w is in P. Note that →G is a binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
on the strings of Σ.
The language of G, denoted 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
Transitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
of →G.
Example
The prefix grammar- Σ = {0, 1}
- S = {01, 10}
- P = {0 → 010, 10 → 100}
describes the language defined by the regular expression
Regular expression
In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...