Regular tree grammar

In theoretical computer science and formal language theory, a regular tree grammar is a formal grammar that describes a set of directed trees, or terms.

[1] A regular word grammar can be seen as a special kind of regular tree grammar, describing a set of single-path trees.

The tree language generated by G1 is the set of all finite lists of boolean values, that is, L(G1) happens to equal TΣ1.

The grammar G1 corresponds to the algebraic data type declarations (in the Standard ML programming language): Every member of L(G1) corresponds to a Standard-ML value of type BList.

The set L(G2) has no datatype counterpart in Standard ML, nor in any other functional language.

Example derivation tree from G 1 in linear (upper left table) and graphical (main picture) notation