COMP 1002

Assignment 4

More Induction!

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 attempt to solve 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./nWith this understanding please complete the following questions:

1. Theory

A Kirby string is defined recursively as follows:

i) (^o^) is a Kirby string.

ii) (ToT) is a Kirby string.

iii) if A is a Kirby string, then is a Kirby string.

That is concatenated with A concatenated with >.

iv) if A, B, C are all Kirby strings, then A...B...C is a Kirby string.

That is A concatenated with ... concatenated with B concatenated with ...

concatenated with C.

v) Nothing else is a Kirby string.

a) Give a Kirby string that requires the use of rule iv, but such that K₁, K₂, K3

are all different Kirby strings.

Explain how to derive your Kirby string using the rules given.

b) Disprove the following statement:

Every Kirby string has the o character in the centre of the Kirby string.

c) Prove by structural induction that every Kirby string has an odd number of

characters.