Example 1:
For the domain E:Expression and its BNF rule:
E ::= zero | E1*E2 | (E) show that all members of Expression have
the same number of left and right parentheses.
Proof:Consider the three options:
zero- there are zero occurrences of both left and right
E1 * E2: by the inductive hypothesis, E1 has say m left parentheses and m right parentheses, and similarly E2 has n left and n right parenthesis. Then E1*E2 has m + n left and m + n right parentheses.
(E): by the inductive hypothesis, if E has m left and m right parentheses then (E) has m+1 left and m+1 right parentheses