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),
$Z$ is the starting non terminal, and
$P$ is a set of productions of the form $A \rightarrow 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) \times 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 \rightarrow 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.

[edit] External links

Tree Automata Techniques and Applications

Categories: Formal languages

Views

Interaction

Search