The collection of strings over the alphabet is the smallest set satisfying

, and

if a and w then aw .

We say that a string p is a prefix of a string w if there is some string s such that w = ps. For example, is a prefix for every string in and the string ab is a prefix of abac {a, b, c} .

a) Define a recursive function length : 7 N such that length(w) is the length of the string w.

b) Define a recursive function is_prefix : 7 Bool such that

is_prefix(p, w) = True if p is a prefix of w False otherwise.

c) Prove, using the principal of structural induction for strings. that for all strings x, y if is_prefix(x, y) = True and length(x) = length(y) then x = y.