COMP $1002$

Assignment $4$

Recursion and Structural Induction

Due Friday July $12$th at $11$:$59$pm Newfoundland Time

No late submissions are accepted.

Please read the following important notes:

$$ Your assignment must be completed on your own.

Sharing solutions, looking for and$/$or copying solutions from unauthorized sources,

and posting the assignment questions online are all forms of academic misconduct.

Committing an act of academic misconduct will result in a grade of $0$

and reported to the department head.

$$ Only one problem set will be graded and it will be selected at random. Students

who attempt to solve the problem but do not get a perfect score are allowed to

submit a Reflection to obtain bonus marks on their Assignment.

If you do not submit a solution to the selected problem set, then you

cannot submit a reflection.

$$ Please submit a file for each problem set and clearly state the problem set in the

file$$s name. Acceptable file formats are PDF$,$ JPG$,$ or PNG$.$

Do not include your name$/$id in your submission.

$$ If your solutions are handwritten, please ensure your solution is legible.

Double check both your image quality and handwriting.

If we cannot read your solution, then you will get a mark of $0.$

$$ While writing your solutions, you will be graded on both your approach and

correctness. A given problem may be solvable in a number of different ways $-$ we

will not grade you on efficiency. That being said, if a problem says to use a specific

technique $($i$.$e$.$ Natural Deduction$)$ then you must solve it using this technique.

With this understanding please complete the following questions:

$1.$ Theory

A Kitkat string is a defined recursively as follows:

i$)$ meow is a Kitkat string.

ii$)$ if P is a Kitkat string, then meP ow is a Kitkat string.

iii$)$ if P is a Kitkat string, then giveP food is a Kitkat string.

iv$)$ Nothing else is a Kitkat string.

a$)$ Give the derivation for givemegivemeowfoodowfood.

b$)$ Disprove: The length of the Kitkat string is always $2$k$,$ for some k in Z$.$

c$)$ Prove by structural induction on the Kitkat string that the substring meow

will always be in the centre of the Kitkat string. In other words, prove that

there is an equal number of characters on both sides of the meow.