Induction

General Induction Example 3

Problem: Prove that no string x in the language AE defined below contains the substring )(.

Let be the alphabet {i, (, ), +, -}. The language AE over is defined recursively as follows:

Basis:
Induction: For arbitrary strings x and y of AE, the strings (x+y) and (x-y) are both in AE.
ExtremalClause: As usual. Omitted.

AE is a language of arithmetic expressions.

Proof:
The proof mirrors the recursive definition of AE.

Basis: Obviously i does not contain )(.
Induction: Assume that arbitrary strings x and y of AE do not contain )(.
Then neither (x+y) nor (x-y) contain )(.
For prefixing x with (, y with + or - does not create )(. Similarly appending + or - to x, or ) to y does not produce )(.
Thus both (x+y) and (x-y) do not contain )( as a substring.
End of Proof.