Induction
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.