T Naughton, NUIM
Back to CS403/SE307/CS355 home

Lab 2 - Turing machine programming (continued)

Here you will build on what you learnt in the previous lab about TM programming. Once again, we will use Paul Ming's Perl VTM .

Machine 2.1 Construct a TM that accepts the language L of words over alphabet {a,b} that end with an a. More formally, this language is L = {w : w in {a,b}*, w ends with at least one a}. In lexicographical order, L = {a, aa, ba, aaa, aba, baa, bba, aaaa,...}. Your TM should halt in state 99 if and only if w is in L. If w is in not in L, it does not matter what your TM does, as long as it does not halt in state 99.

Note, accept means the same thing as Sipser's term recognise.

Machine 2.2 Write a version of Machine 2.1 that decides the language. To decide the language, your TM must accept words in L and reject words not in L. Let 99 be your accepting state and let 50 be your rejecting state. Furthermore, the tape head must be back at the start of the word when your TM halts.

Example Machine 2.A Write a TM that accepts the language L = {w1w : w in {0}*}. To accept a word the TM should go into state 99.

So, in lexicographical order, L = {1, 010, 00100, 0001000, 000010000,...}. Also, note that because the question doesn't specifically ask us not to delete the input, it is OK for us to delete it if we want.

Sample solution (in pseudocode).

On input word w:
1) Remove a 0 from the left end of the word and a 0 from the right end of the word
2) Keep repeating this as long as you can, making the word shorter and shorter
3) If you are left with a single 1, then accept

This sample solution again (this time in TM code). The start state is 00.

#Si,R, Sf, W, M
#--------------
00, 0, 01, _, R # remove a 0 from the left end
01, 0, 01, 0, R # move to end of word
01, 1, 01, 1, R # move to end of word
01, _, 02, _, L # at end of word step left
02, 0, 03, _, L # remove a 0 from the right end
03, 0, 03, 0, L # move back to beginning of word
03, 1, 03, 1, L # move back to beginning of word
03, _, 00, _, R # at beginning of word, start all over again
00, 1, 04, _, R # no more zeros on the left, so check on right
04, _, 99, _, R # no more zeros on right either, so accept

Try a few inputs of your own, including "____010____", "____1____", and "___000010000___" (which should all be accepted), and "____00____", "________", "____001000____", and "___000100___" (which should not be accepted -- i.e. should halt in any state except 99).

Machine 2.3 Modify the code of Sample Machine 2.A so that it decides the language. To reject a word the TM should go into state 50.

Example Machine 2.B Write a TM that accepts the language L = {w : w in {0,1}*, |w|>=1, w begins and ends with the same symbol}. In lexicographical order, L = {0, 1, 00, 11, 000, 010, 101, 111, 0000, 0010, 0100, 0110,...}. To accept a word the TM should go into state 99.

Sample solution (in pseudocode).

On input word w:
1) Remember if the first symbol is 0 or 1
2) Skip to the end of the word
3) If the same symbol is at the end, then accept

This sample solution again (this time in TM code). The start state is 00.

#Si,R, Sf, W, M
#--------------
00, 0, 01, 0, R # state 01 means we read a 0
00, 1, 02, 1, R # state 02 means we read a 1
01, 0, 01, 0, R # move to end, remembering we read 0
01, 1, 01, 1, R # move to end, remembering we read 0
01, _, 03, _, L # move to final symbol, remembering we read 0
02, 0, 02, 0, R # move to end, remembering we read 1
02, 1, 02, 1, R # move to end, remembering we read 1
02, _, 04, _, L # move to final symbol, remembering we read 1
03, 0, 99, 0, R # it was the appropriate symbol, so accept
04, 1, 99, 1, R # it was the appropriate symbol, so accept

Machine 2.4 Construct a TM that accepts the language L of words over alphabet {0,1} that are palindromes (read the same forwards as in reverse). More formally, L = {w : w in {0,1}*, w=w^R}. In lexicographical order, L = {e, 0, 1, 00, 11, 000, 010, 101, 111, 0000,...}. To accept this language, the TM must halt in state 99 if and only if the input is in L.

Machine 2.5 Construct a TM that accepts the language L = {w in {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 2.6 Modify the code of the first example (Sample Machine 2.A) so that when the TM halts the tape head is at the beginning of the input word. (This means you can't delete the input! Hint: rather than overwriting the 0s with blanks, try overwriting them with an 'x' and then as a final step replace all 'x's with 0s again.)