CS 373 - Fall 1997 - NMG

CS 373 – Fall 2003 – ********** solution ***** **********

November 12, 2003

Homework Assignment 9 - Turing Machines

Due 11/21/03 (Friday)

Problems related to chapter 9

1.Consider the Turing Machine:

M = ( {q0, q1, q2, q3}, {a, b}, {a, b, #,  }, , q0, , { q3} ), where  is given by:

 (q0, a) = (q1, a, L)

 (q0, b) = (q0, b, R)

 (q0, ) = (q0, , R)

 (q0, #) = (q0, #, R)

 (q1, a) = (q1, a, L)

 (q1, b) = (q2, b, R)

 (q1, ) = (q1, , L)

 (q1, #) = (q1, #, R) //typo fixed

 (q2, a) = (q2, a, R)

 (q2, b) = (q2, b, R)

 (q2, ) = (q3, , L)

 (q2, #) = (q2, #, R)

(a) Trace the computation of M (until it halts if it halts) starting with the instantaneous description: #aq0bbbbaba
(b) Give an informal description of what M does when started in state q0 at any position on the entire tape. Assume the initial tape content is a random sequence of symbols from

 = {a, b, #,  }, and there may be an arbitrary and unbounded number of these symbols on the tape.

2.[COMMENT1] Design a Turing machine which accepts the language:

L = {anbman+m : n  0, m  1}. Use pseudo code or very clear English to give an overview or description of the algorithm. Finally you must give a “low level” delta function implementation of this TM. The transition functions must be clearly commented. Remember that in addition to writing the code for the path to accepting a string, you must account for all the ways a string could be rejected. There should be three reasons for rejection to be accounted for by your code: (1) the suffix of “a’s” is too long (too many a’s: larger than n+m), (2) the suffix of a’s is too short (not enough a’s, less than n+m), (3) the over all format is wrong: string does not have a distinct prefix of a’s, a mid field of b’s and a suffix of a’s.

Design a turing machine which would accept the language:

L = { ww : w  (a, b)+ }

Instead of using a low level delta function implementation, you may use a high level outline of the algorithm for the design. The outline must be clear enough to allow a person to unambiguously write the transitions functions for this automaton.

You just “solved” a problem previously unsolvable without the power of a Turing Machine. If this language is not context free (see example 8.2), then what is it? What are the implications of this problem in the theory of languages? Do you think there are languages even beyond the TM? – I thought that TM’s were supposed to be the supermen of the automata world.

4. [COMMENT2]Design a Turing machine which computes the function:

f(x,y) = x-y, where x and y are signed unary numbers.

You may use pseudo code and “box” diagrams to describe the algorithm.. Pseudo code may be English like, or even very clear English - BUT IT MUST BE CRYSTAL CLEAR AND COMPLETE. x and y in this problem are two signed unary numbers. You may assume that a signed unary number is represented by a sign symbol which is written just to the left of the unary number (simple use the + and – symbols). The subtraction is “algebraic” subtraction on signed numbers. After changing the sign of the second number: It adds the numbers if the resulting signs are the same and the sign of the answer is the sign of either number, and if the resulting signs are different, it take the absolute value of the difference and assigns the sign of the larger number.

For your box diagram you may assume that you have the following “off the shelf” TM “boxes”

-An adder such as given in the example in the book (unary numbers)

-A subtractor which puts out the magnitude of the difference between two positive unary numbers.

-A compare box as given in the example in the book.

-A box which checks the signs of the two numbers – give some explanation/pseudo code on how this works
The “box” with the off-the-shelf TMs should show how the whole thing works. Indicate how these are connected and linked together to so one box flows into another and there is no conflict of states.

5. Design a standard Turing Machine that converts a sequence of n a’s into n2 a’s. In other words this TM does the function: f(an) = an^2 , n  0. where n^2 is the same as n2. …. problem with “double superscripts”. Note that the n = 0 case gives f() =  . Assume that tape is initially:

q0aaa…a = q0an (n a’s), and the final tape should look like:

qfaaa…a = qfan^2 (n2 a’s). This problem is similar to example 9.14 in the text. Consider two logical loops: an outer loop so you could write a string of a’s at the end of the current string of length equal to the original string (n), for each of the symbols in the original string, and an inner loop for creating this string. Auxiliary temporary symbols will needed to keep track of where you are in both of these loops. When done you should have only one symbol in the string, namely ‘a’.

Initially use very clear pseudocode or an English description, followed by a low level “delta” function design.

Solutions:

Problem 1:

|- #abbbq1baba |- #abbbbq2aba |- #abbbq3baba
(b) The Machine moves to the right until an “a” is detected (this part may go on forever), then it moves to the left until a “b” is detected (if it hits the # symbol before seeing a “b”, it will go into an infinite loop on this step), Then it moves to the right until a blank is detected (this step will terminate), then the machine halts.

problem 2:

Outline of solution:

problem 2 continued:

problem 2 continued):

problem 2 continued

Problem 3 Design a TM which accepts the language L = { ww : w  {a, b}+.

Rough idea:

The Turing machine to solve this problem works in three phases. In the first phase, a “c” is written at the end of the input string. In the second phase, the “c” is progressively moved one character to the left until there are as many characters of the original input on either side of the “c”. To aid in doing this, characters that have been accounted for are changed from their original symbols to substitute symbols, such as replacing a with x and b with y. If an odd number of characters is discovered on this pass, the machine rejects. Once the c symbol is positioned to the middle of the string, we start phase 2 in which we scan back and forth similar to the anbn problem and match corresponding symbols on either side of the c. As soon as a mismatch of a symbol pair is detected, the string is rejected. When comparing a symbol on one side of the c with the corresponding on the other side, you could ‘remember” what you are comparing by having unique states for distinct symbols being compared. This will require new substitute symbols such as u replacing x or a, and v replacing y or b. In the 3rd phase, the strings to either side of

the “c” are converted back to their original forms character by character.

Problem 4.

Problem 5:

(10 points) Design a standard Turing Machine that converts a sequence of n a’s into n2 a’s. In other words this TM does the function: f(an) = an^2 , n  0. where n^2 is the same as n2. …. problem with “double superscripts”. Note that the n = 0 case gives f() =  . Assume that tape is initially:

q0aaa…a = q0an (n a’s), and the final tape should look like:

pseudocode:

General idea: if the string has n a’s (n > 0), then copy the string n-1 times after input string (outer loop), if n = 0, do nothing. “Copying the string” means to write an a after the current string for each symbol in the original string (inner loop).

Move right one, if head is on a blank, then input is empty – reset head and halt

else write a ‘b’ … the b’s keep track of how many times we copy the string (outer loop).

Write a b over the next a after the initial b – skip 1st b due to n-1 copies.

Now by scanning left and right, write an I for each position (symbol) in the original input string (this results in n I’s for each inner loop). Go back left to the last b written and mark the next a with a ‘b’ and again write an I for each position in the original input string. When you are in the process of writing n I’s, by cycling back and forth between the position in the input string and the I field (inner loop), you will have to temporarily replace the b’s and a’s in the original input with d’s and c’s respectively and then converted back to b’s and a’s after each inner loop. This is to distinguish between where you are in the inner and outer loops. This process continues until all a’s have been replaced by b’s. Finally, all the temporary symbols are converted to a’s and the head is reset to the blank before the final string.

Problem 5 continued:

TM code:

D represents the symbol 

B represents the symbol 

D(q0, B) = (q1, B, R)// read initial space

D(q1, B) = (qf, B, L) // empty string – halt

D(q1, a) = (q2, b, R)// mark 1st a in outer loop

D(q2, a) = (q3, b, L)// mark 2nd or beyond “a” in outer loop

D(q2, b) = (q2, b, R)

D(q2, B) = (q7, B, L)

D(q2, I) = (q7, I, L)

D(q3, a) = (q3, a, L)//move left thru a’s(reset head to left)

D(q3, b) = (q3, b, L)//move left thru b’s(reset head to left)

D(q3, d) = (q4, d, R)// hit a d move right - inner

D(q3, c) = (q4, c, R) // hit a c move right - inner

D(q3, ) = (q4, , R)//no more b’s

D(q3, I) = (q3, I, L)//move left thru I’s(reset head to left)

D(q4, b) = (q5, d, L)//change b to d outer

D(q4, a) = (q5, c, L)//change a to c outer

D(q4, I) = (q5, I, L)// end of inner loop just wrote – ran out of d’s and c’s

D(q5, a) = (q5, a, R)// move thru remaining a’s

D(q5, b) = (q5, b, R)// move thru remaining b’s

D(q5, c) = (q5, c, R)// move thru remaining c’s

D(q5, d) = (q5, d, R)// move thru remaining d’s – redundant?

D(q5, I) = (q5, I, R)// move thru remaining I’s

D(q5, ) = (q3, , L)// create I at end for a ‘d’

D(q6, a) = (q6, a, L)// redundant?

D(q6, b) = (q6, b, L)

D(q6, c) = (q6, a, L)// convert c’s to a’s & go left

D(q6, d) = (q6, b, L)// convert d’s to b’s & go left

D(q6, I) = (q6, I, L)// go thru I’s

D(q6, ) = (q2, , R)//

D(q7, ) = (q8, , L)

D(q7, ) = (q7, b, R)

D(q7, I) = (q7, I, R)

D(q8, ) = (qf, , S)

D(q8, a) = (q8, a, L)

D(q8, b) = (q8, a, L)

D(q8, I) = (q8, a, L)

[COMMENT1]Based on problem 9.1.7e used for F97 semester

[COMMENT2]Based on problem 9.1.10b used for F97 semester