CS370 - Computation and Complexity

NUIMCrest CS370 - Computation and Complexity
Department of Computer Science
National University of Ireland, Maynooth

Lab test 1 - Turing machine programming

For this lab test, remove everything from your desk except pens and pencils. Write your answers on this question sheet. You have 45 minutes. Make sure to sign the attendance sheet when you hand up this sheet at the end.

Name: _____________________________________________

Student number: _________________________________________

Class (Science, CSSE, Arts, MCompSci, International): _________________

1. The following TM claims to recognise the language L₁ = {aⁿbⁿaⁿ : n $>=$ 0}. However, three rows of the table of behaviour are missing that stop the TM from working properly. Give these three rows. The start state is 00. The accept state is 99. The symbol _ denotes a blank. [6 marks]

#Si,R, Sf, W, M #-------------- 00, a, 01, _, R 01, a, 01, a, R 01, b, 02, X, R 02, b, 02, b, R 02, a, 02, a, R 02, _, 03, _, L 03, a, 04, _, L 04, a, 04, a, L 04, b, 04, b, L 04, X, 04, X, L 04, _, 00, _, R 00, X, 98, X, R 98, _, 99, _, R

2. Explain in a few sentences of English how the TM in Question 1 recognises L₁. [2 marks]

3. The following TM claims to recognise the language L₂ = {w : w $in$ {a,b}*, w contains an equal number of as and bs}. However, three rows of the table of behaviour are missing that stop the TM from working properly. Give these three rows. The start state is 00. The accept state is 99. The symbol _ denotes a blank. [6 marks]

#Si,R, Sf, W, M #-------------- 00, a, 01, X, R 00, b, 03, X, R 00, X, 00, X, R 01, X, 01, X, R 01, b, 02, X, L 02, X, 02, X, L 02, a, 02, a, L 02, b, 02, b, L 03, X, 03, X, R 03, b, 03, b, R 02, _, 00, _, R

4. Explain in a few sentences of English how the TM in Question 3 recognises L₂. [2 marks]

Below is a template for the kind of pseudocode TM we have been using in lectures. In all tests including the final exam, unless you are specifically asked to give the full table of behaviour for a TM, you can use this kind of pseudocode TM.

Below is a template for the kind of way we have proved that languages are decidable (respectively, Turing-recognisable) in lectures.

Proof that language L is decidable (respectively, Turing recognisable): We prove that L is decidable (respectively, Turing recognisable) by showing the existence of a TM M that decides (respectively, recognises) L. Give pseudocode TM here, called M. Since M decides (respectively, recognises) L then this proves that L is decidable (respectively, Turing recognisable).

5. Prove that L = {(a,b) : a,b $in$ $N$ , a > b} is decidable. [2 marks]

6. Prove that R_TM = { $<$ M,w $>$ : M is a TM and w is a word and M rejects w} is Turing-recognisable. [6 marks]

End of sheet