Example:Inductive definition of the set of trees
- Rule 1: The empty tree is in
- Rule 2: If and are trees, then the tree with value , left child and right child is in T.
We often think of trees pictorially; in this case we might give a BNF definition of as follows:
However, it is also useful to write trees symbolically; in this case we might defineas follows:
Using the first definition, the following is an example tree:
Using the second definition, we would write this as