Example:Inductive definition of the set of expressions

From CS2800 wiki

Mathematical expressions of various kinds are often defined inductively. For example, one might define a set of arithmetic expressions by the rules

[math]\begin{align*} e &\href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=Expr&action=edit&redlink=1}{Expr} \href{/cs2800/wiki/index.php/BNF}{::=} n \href{/cs2800/wiki/index.php/%5Cmid}{\mid} e_1 + e_2 \href{/cs2800/wiki/index.php/%5Cmid}{\mid} -e \href{/cs2800/wiki/index.php/%5Cmid}{\mid} e_1 * e_2 \\ n &\href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \end{align*} [/math]

Here, we are treating "+", "*", and "-" as uninterpreted symbols. For example, [math](3 + (4*5)) + (-2) [/math] is an expression, formed from the substructures [math](3+(4*5)) [/math] and [math](-2) [/math] using the "+" rule. Most programming languages have a similar inductive definition, allowing us to formally model programs.