Regular tree grammar
From Wikipedia, the free encyclopedia
In Computer Science, a regular tree grammar is a formal grammar that allows to generate trees.
[edit] Definition
A regular tree grammar G is defined by the tuple:
G = (N,Σ,Z,P),
where
- N is a set of non terminals,
- Σ is a ranked alphabet (i.e., an alphabet whose symbols have an associated arity),
is the starting non terminal, and- P is a set of productions of the form
, where 
, and 
.
For this grammar G, we define also the relation 
as follows.
For every 
, if there is a context 
and a production 
such that:
- t1 = S[A], and
- t2 = S[t].
The tree language generated by G is the language
.
Where 
denotes successive applications of 
. Such languages are called Tree languages.
