Regular tree grammar

In Computer Science, a regular tree grammar is a formal 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 associated arity),
* $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 languages.

External links

* [http://www.grappa.univ-lille3.fr/tata/ Tree Automata Techniques and Applications]