Inductively defined set
- Rule 1: Z as standing for "zero") (We think of
- Rule 2: If S stands for "successor"; you can think of </math>S~n</math> it as representing "1 + n", although we will define + in terms of S instead of the other way around). then (
Thus the elements of are . You can then define as , as , and so on.
A BNF definition looks like this:
The rules define the various ways of constructing objects in the set. Any uses of the variables on the left hand-side of any of the equations, should be replaced by already-constructed elements of the corresponding set.
The BNF definition.symbol is simply used to indicate that the definition is a
For example, if, then
To add further detail, we can show thatas follows:
- 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
Here, we are treating "+", "*", and "-" as uninterpreted symbols. For example, substructures and using the "+" rule. Most programming languages have a similar inductive definition, allowing us to formally model programs.is an expression, formed from the