Compilers: Principles and Practice by Pearson

404 Appendix A

For example,

The relation “less than or equal to” on the set of natural numbers:

c

Reflexive: For every i ∈ N, i ≤ i holds.

c

Antisymmetric: For every i and j (i ≠ j), exactly one of i < j and j < i holds.

c

Transitive: If i ≤ j and j ≤ k hold, then i ≤ k holds.

Thus, ≤ is a partial order on N.

A.1.6 Inductive Definitions

Recursive definition in more general is called Inductive Definition.

Let S be an infinite set to be defined.

An inductive definition of S consists of the following three components:

Base Clause (or Basis): To establish that a finite number (usually one) of certain objects are

elements in the set S;

Inductive Clause (or ...