T Naughton, CS NUIM, Back to SE307 home

You have 40 minutes for both questions. Marks will be lost for illegible submissions so please write clearly. Full marks will be awarded for a fully functional submission. Comments are not necessary but may allow you to get some marks if your submission is incorrect.

Q1 Construct a Turing machine (TM) to add 3 to a unary number. Initial state: the tape head is positioned at the beginning of the input (for example, "11"). Halting state: the tape head has positioned itself at the beginning of the output (in this case, "11111"). [5 marks]

Q2 Construct a TM to recognise the language L of palindromes over the alphabet {a,b}. A palindrome is a word that reads the same forwards as backwards. For example, "babab", "abba", "a", and the empty word are words in L. The words "ab", "aabb", and "abab" are not in L. Initial state: the tape head is positioned at the beginning of the input. (Each input will be a word over {a, b}.) Halting state: the tape head is positioned at a `T' if the input word is in L and is positioned at an `F' if the input is not in L. [20 marks]