- Source: 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 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 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 finite 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
=
v
u
,
y
=
w
u
{\displaystyle 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
)
{\displaystyle 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.
Example
The prefix grammar
Σ = {0, 1}
S = {01, 10}
P = {0 → 010, 10 → 100}
describes the language defined by the regular expression
01
(
01
)
∗
∪
100
∗
{\displaystyle 01(01)^{*}\cup 100^{*}}
See also
Regular grammar
References
Kata Kunci Pencarian:
- Awalan bilangan
- Daftar istilah komputer
- Bahasa Navajo
- Rumpun bahasa Semit Barat Laut
- Bahasa Dhao
- Prefix grammar
- Prefix
- Numeral prefix
- English prefix
- Regular grammar
- Sumerian language
- Prefixes in Hebrew
- List of formal language and literal string topics
- Meta (prefix)
- Modern Hebrew grammar
