Computer Science Canada recursive definition help |
| Author: | bladeb2k [ Sun Aug 19, 2007 10:22 am ] |
| Post subject: | recursive definition help |
basically this is 2 questions i have to do which is the final part of a paper that started with me having to design a turing machine that checks that strings of binary digits are formatted correctly with { and } formatted correctly. ie 10 {100 } 1 is ok but }101{1} is not. 4. Assuming that the meaning of ?number? in the above grammar is understood complete the following recursive definition of valid input by filling in the blanks. 1. A number is a valid input 2. If X is a valid input so is --------------- 3. If X and Y are valid inputs so is ------------------ 4. These represent all legal inputs. Using these definition show that the following are legal inputs a) 1, {1} b) {1,{1}} c) 1 Is {} a legal input according to this definition? Justify your answer. 25 marks |
|