- Regular tree grammar
In
Computer Science , a regular tree grammar is aformal grammar that allows to generate trees.Definition
A regular tree grammar G is defined by the tuple:
G = (N, Sigma, Z, P),
where
* N is a set of non terminals,
* Sigma is a ranked alphabet (i.e., an alphabet whose symbols have an associatedarity ),
* Z is the starting non terminal, and
* P is a set of productions of the form A ightarrow t, where A in N, and t in T_Sigma (N).For this grammar G, we define also the relation Rightarrow_G subseteq T_Sigma (N) imes T_Sigma (N) as follows.
For every t_1, t_2 in T_Sigma (N), t_1 Rightarrow_G t_2, if there is a context S in C and a production A ightarrow t in P such that:
* t_1 = S [A] , and
* t_2 = S [t] .The tree language generated by G is the language
L(G) = { t in T_Sigma | Z Rightarrow_G^* t}.
Where Rightarrow_G^* denotes successive applications of Rightarrow_G. Such languages are called
Tree language s.External links
* [http://www.grappa.univ-lille3.fr/tata/ Tree Automata Techniques and Applications]
Wikimedia Foundation. 2010.