T Naughton, NUIM
Back to SE307 home

Lab 3 - Turing machine programming (language acceptance)

In this lab you will continue to develop your Turing machine (TM) programming skills. The problems will be based on the concept of language acceptance. For each of the problems, accepting a language L means the TM must halt in state 99 iff input word wÎL. As usual, it does not matter what the TM does if wÏL, as long as it does not halt in state 99. Once again, you should use Paul Ming's Perl-based Virtual Turing Machine (VTM). First, a solution to the final problem from last week.

Machine 3.A (Solution to 2.4 from last week.) Construct a TM that accepts the language L of words over S={x,1} where each word is a triple (3-tuple) of unary numbers describing a valid addition expression. Each word consists of three unary numbers separated by two x symbols. If the word is in L then the addition of the first two should give the third. This means L={xx, x1x1, 1xx1, 1x1x11, 1x11x111, 11x1x111, 11x11x1111, 11x111x11111,...}. More formally, this language could be written as L={w : w=axbxc, a,b,cÎ{1}*, |a|+|b|=|c|}. To accept this language, the TM must halt in state 99 iff wÎL. One valid table of behaviour corresponding to such a machine would be as follows. [The basic idea for this solution is as follows: replace the first x with a 1, remove a 1 from the beginning of the word, and then check that the word is a palindrome.]

#Si,R, Sf, W, M
#--------------
00, 1, 00, 1, R # replace first x with 1
00, x, 01, 1, L # replace first x with 1 (cont.)
01, 1, 01, 1, L # remove 1 from beginning of word
01, _, 02, _, R # remove 1 from beginning of word (cont.)
02, 1, 03, _, R # remove 1 from beginning of word (cont.)
03, 1, 04, _, R # check if a palindrome
03, x, 07, _, R # check if a palindrome (cont.)
04, 1, 04, 1, R # check if a palindrome (cont.)
04, x, 04, x, R # check if a palindrome (cont.)
04, _, 05, _, L # check if a palindrome (cont.)
05, 1, 06, _, L # check if a palindrome (cont.)
06, 1, 06, 1, L # check if a palindrome (cont.)
06, x, 06, x, L # check if a palindrome (cont.)
06, _, 03, _, R # check if a palindrome (cont.)
07, _, 99, _, R # check if a palindrome (cont.) and halt
# end of machine

Machine 3.1 Construct a TM that accepts the language L of words over S={x,1} where each word is a triple (3-tuple) of unary numbers describing a valid subtraction expression. Each word consists of three unary numbers separated by two x symbols. If the word is in L then the subtraction of the second number from the first should give the third. Assume that the first number will always be greater than or equal to the second number. This means L={xx, 1xx1, 1x1x, 11xx11, 11x1x1, 11x11x, 111xx111, 111x1x11,...}. More formally, this language could be written as L={w : w=axbxc, a,b,cÎ{1}*, |b|£|a|, |a|-|b|=|c|}.

Machine 3.2 Construct a TM that accepts the language L={wÎ{0,1}* : w has an equal number of 0s and 1s}. Therefore, L={e, 01, 10, 0011, 0101, 0110, 1010, 1100, 000111, 001011, 001101, 001110, ...}.

Machine 3.3 Construct a TM that accepts the language L={wÎ{[,]}* : w is a string of properly nested and concatinated brackets}. Therefore, L={e, [], [[]], [][], [[[]]], [[]][], [][[]], [][][], [[[[]]]], [[[]]][], ...}. In case the symbols '[' and ']' cause problems within the PERL interpreter, in your implementations replace them with 'a' and 'b', respectively.