T Naughton, NUIM
Back to SE307 home

Lab 1 - 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. 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 2.A (Solution to 1.5 from last week.) Construct a TM to multiply two unary natural numbers. Initial state: the tape head is positioned at the beginning of the input, which consists of two unary numbers separated by a single space (for example, "111 11"). Halting state: the tape head is positioned at the beginning of the output (in this case, "111111"). One valid table of behaviour corresponding to such a machine would be as follows. [The basic idea for this solution is as follows: for every `1' in the first number m, the second number n is copied and appended to itself. When there are no more `1's left in m, there will be (m+1) copies of n. At this stage, one copy of n will be deleted. This neatly takes care of the situation where m is zero. During copying, temporary symbol `X' is used to keep track of how much of n has been copied so far, and temporary symbol `Y' is used when appending symbols. This Turing machine requires 4 symbols and 12 states. Can you do any better (either fewer symbols, fewer states, or fewer transition rules)?]

#Si,R, Sf, W, M
#--------------
00, 1, 04, _, R # delete a 1 in m and proceed to make a copy of n
00, _, 01, _, R # if m is blank, delete n
01, 1, 01, _, R # if m is blank, delete n (cont.)
01, _, 99, _, L # after deleting n, halt if m was blank
01, x, 02, 1, R # after deleting n, convert copies back to 1s
02, x, 02, 1, R # convert copies back to 1s (cont.)
02, _, 03, _, L # convert copies back to 1s (cont.)
03, 1, 03, 1, L # convert copies back to 1s (cont.)
03, _, 99, _, R # convert copies back to 1s (cont.) and halt
04, 1, 04, 1, R
04, _, 05, _, R
05, 1, 06, y, R
05, x, 10, x, L
05, _, 07, _, L
07, _, 08, _, L
08, 1, 08, _, L
08, _, 99, _, R
06, 1, 06, 1, R
06, x, 06, x, R
06, _, 09, x, L
09, x, 09, x, L
09, 1, 09, 1, L
09, y, 05, y, R
10, y, 10, 1, L
10, _, 11, _, L
11, 1, 11, 1, L
11, _, 00, _, R
# end of machine

Language acceptance

Definition 2.0 - A symbol is a single character such as a letter or digit.

Definition 2.1 - A set is a collection of elements. The order of the elements is not important. Elements are not repeated. Elements of sets can be symbols or other sets. Therefore {1, a, {1}} and {a, {1}, 1, a} would be the same sets. Sets can be empty, nonempty and finite, or infinitely large. The size of a set is referred to as its cardinality. We use braces {...} to denote a set.

Definition 2.2 - A sequence or tuple is a collection of elements for which order is important. Elements may be repeated in a tuple. Therefore (1, {2}, 2) and (1, {2}, 2, 2) are distinct tuples. We use parentheses (...) to denote a tuple. A tuple of length two is called a pair, a tuple of length three is called a triple, and so on. In general, a tuple of length k is called a k-tuple.

Definition 2.3 - An alphabet S is a nonempty finite set of symbols.

Definition 2.4 - A string or word is a tuple of symbols. For this course, all words have finite length. The length of a word w is denoted |w|. A word over an alphabet S is a word made up of symbols from S. The zero-length word (empty word) is a valid word over any alphabet. The empty word over an alphabet S is denoted with a symbol not found in S: usually e. Because each symbol is one character long, we can usually omit the parentheses and commas when specifying a word. For example, let alphabet S={a,b,c}. Let w be a word over S and let it be (a, b, b, a). w is commonly written without parentheses as abba.

Definition 2.5 - The set of all words over an alphabet S is denoted S*. For example, let S={a,b}, then S*={e, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba,...}. For all nonempty finite S, S* is infinite and S* contains e.

Definition 2.6 - A language is a set of words. A language may be infinite. A language may be empty. A language over an alphabet S is a subset of S*.

Definition 2.7 - A machine accepts a language L if it outputs `T' (or goes into an appropriate state) if and only if (iff) it is presented with a word w in L. It does not matter what the machine does if it is presented with a w not in L (as long as it doesn't accept it too!).

Machine 2.1 Construct a TM that accepts the language L of words containing zero or more a symbols and no other symbols. Only symbols a and b are permitted as input. More formally, this language could be written as L={e, a, aa, aaa,...} or as L={w : w in {a,b}*, w contains zero bs}. To accept this language, the TM must halt with the tape head under a symbol `T' iff w is in L. This means that it does not matter what the TM does in response to an input that is not a word in L (i.e. it is perfectly respectable for the TM to crash or to run forever if it is presented with the input word aab, for example) as long as it doesn't halt under a `T' if the word is not in L.

Machine 2.2 Construct a TM that accepts the language L of words over S={a,b} that end with an a. This means L={a, aa, ba, aaa, aba, baa, bba, aaa,...}. More formally, this language could be written as L={w : w in {a,b}*, w ends with at least one a}. To accept this language, the TM must halt in state 99 iff w is in L. This means that in response to an input word not in L the TM may do anything at all (halt in any state or go into an infinite loop) except halt in state 99. This also means that that the tape head can be positioned anywhere when it halts.

Machine 2.3 Construct a TM that accepts the language L of words over S={0,1} that are palindromes (read the same forwards as in reverse). This means L={e, 0, 1, 00, 11, 000, 010, 101, 111, 0000,...}. More formally, this language could be written as L={w : w in {0,1}*, w=w^R}. To accept this language, the TM must only halt in state 99 iff w is in L.

Machine 2.4 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 in {1}*, |a|+|b|=|c|}. To accept this language, the TM must halt in state 99 iff w is in L.