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.