T Naughton, NUIM
Back to SE307 home

Lab 3 - Turing machine programming

In this lab you will continue to develop your Turing machine programming skills.

Once again, use Paul Ming's Perl Virtual Turing Machine (VTM).

Construct tables of behaviour for the following Turing machines. Write them on paper first. Use the VTM to test your tables.

Machine 3.A Construct a TM to increment a unary number. Initial state: the tape head is positioned at the beginning of the input (for example, "111"). Halting state: the tape head has positioned itself at the beginning of the output (in this case, "1111").

Machine 3.B Construct a 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").

Machine 3.C Construct a TM to recognise the language aⁿbⁿaⁿ (where n>=0). Initial state: the tape head is positioned at the beginning of the input (for example, "aabbaa"). Halting state: without overwriting any of the input, the tape head has positioned itself to the right of the input where it has written a `T' if the word is in the language, and written an `F' otherwise (in this case, "aabbaaT").

If you are finished early, correct your tables of behaviour from the last lab, and attempt the following problem.

Machine 3.D Construct a TM to syntax check an arbitrary C++ cout statement. Assume that the only text symbols are `a' and `h' and that variable names only use the letters `b' and `a', for example "cout << "aaaha" << baaaaa;". You may also assume that every statement ends with a semicolon. Initial state: the tape head is positioned at the beginning of the cout statement. Halting state: without overwriting any of the input, the tape head has positioned itself to the right of the input where it has written a `T' if the word is in the language, and written an `F' otherwise.
Note: Some simulators may not be able to handle the symbols `<', `"', and `;'. In such cases, substitute the symbols `x', `y', and `z', for example "cout xx yaaahay xx baaaaaz" (without the quotes, of course) would be a valid input.