Construct a Turing machine that generates all strings in reverse lexicographic order between the two provided strings

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Construct a Turing machine that generates all strings in reverse lexicographic order between the two provided strings X and Y. An input will be of the form “X,Y”, where X is an element of {0, 1, 2}+ and Y is an element of {0, 1, 2}*. Your Turing machine must be a single tape, one way infinite, deterministic Turing machine. For this program you can use the left, right, and stay directives. When the Turing machine completes, the tape should contain a comma delimited list of all strings over {0, 1, 2}* in reverse lexicographic order starting with X and ending with Y. When your program completes it should accept the input and position the r/w head at the leftmost symbol of X. For this assignment you may want to use blocks (Turing machine subroutines in JFLAP) to build your Turing machine. Your Turing machine cannot make use of the blank spaces to the left of the input string. You may use the “~” to match any symbol for reading/writing in a transition. Otherwise any transition must read/write a single symbol. You may not use the JFLAP transitions like “(a,b,c}w; w, R)” (stores a symbol in a JFLAP internal variable). You are to use JFLAP version 7.1, which is the one posted on blackboard for this assignment. The previous version of JFLAP has some unhappiness with filenames containing special characters and I don't know all the symbols that cause problems (I stick with alphanumeric and the underscore symbol, and have had problems with $ and # - JFLAP throws an error when trying to save the program after inserting the block). The older version of JFLAP also has some problems with blocks. I will discuss these in class. Some students, 10% or less, had problems with JFLAP and blocks. When I constructed my Turing machine for the assignment, I did not have any problems with blocks.

 

The inputs X & Y will be valid, in the sense that they will be strings over {0, 1, 2} and X will be an element in the list of strings over {0, 1, 2} that is lexicographically larger than Y. Y can be the empty string. That is, an input of “X,” is valid. For what this is worth, this is the easiest of my program 7s.

 

It took me 3 – 4 hours to implement the program and about an hour to test it. I will test your program with 20 or more strings. My implementation uses ∑ = {0, 1, 2, ,} and Γ = {0, 1, 2, ,, $, #, a, b, c, ' '}.

 

My Turing machine works as follow:

1) Insert a $

2) Insert a # to the right of the $ - the # is used to mark the string that is currently being copied to make the next string in the sequence

3) While the newly inserted string does not equal Y

1. Insert a comma to the right of the string having the # to the left of it

2. Copy the string to the right of the # to the right of the comma immediately following it

3. Update the string just copied making it the next string in reverse lexicographic order after the string to the right of the #

1. This is approximately the same as subtracting 1 from the string

4. If the new string is equal to Y, then delete Y (since there are now two copies of it) and the comma to the left of it, change the # to a comma and position the r/w head at the symbol two symbols to the right of the $ and halt and accept

 

My initial version of the program was written to be very inefficient, so that I could easily test my blocks without having full functionality. This was done by having each major block assume that the r/w head was always positioned one symbol to the right of the $ and to always positioned the r/w head one position to the right of the $ when done. Once I had the program working, I modified the blocks to position the r/w head in a place were the next block would start its work. The original version takes over 16,000,000 transitions for an input of “222222,” while the updated program takes less than

 

 

1 of 3 © 2020, Dave Garrison

 

500,000 transitions. For an input of “2222222,” the original version took over 131,000,000 transitions while the updated program takes less than 2,000,000 transitions. Your program should be able to handle an input of “2222222,” with less than 131,000,000 transitions (so that it runs in a reasonable amount of time).

 

My Turing machine uses blocks for the following actions.

• insertLeftTerminator - insert terminator at the left end of the tape (7 states)

◦ Inserts a $ at the left end of the input and shifts the input to the right

◦ Rewinds the tape and leaves the r/w head to the right of the $

• insertCurrentStringMarker - insert current string marker (7 states)

◦ Inserts a # at the left end of the input and shifts the input to the right

◦ Rewinds the tape and leaves the r/w head to the right of the $

• insertCommaAfterComma - insert comma after comma (8 states)

◦ Inserts a comma after the comma that terminates the current string

◦ Leaves the r/w head at the #

• insert0AfterComma - insert 0 after comma (9 states)

◦ Inserts a 0 after the comma that terminates the current string

◦ Leaves the r/w had at the rightmost unprocessed symbol of the current string or the # if all of the symbols of the current string have been processed

• insert1AfterComma - insert 1 after comma (9 states)

◦ Inserts a 1 after the comma that terminates the current string

◦ Leaves the r/w had at the rightmost unprocessed symbol of the current string or the # if all of the symbols of the current string have been processed

• insert2AfterComma - insert 2 after comma (9 states)

◦ Inserts a 2 after the comma that terminates the current string

◦ Leaves the r/w had at the rightmost unprocessed symbol of the current string or the # if all of the symbols of the current string have been processed

• copyCurrentString - copy current string (7 states, 4 blocks)

◦ Inserts a copy of the current string after itself

◦ Uses insertCommaAfterComma, insert0AfterComma, insert1AfterComma, and insert2AfterComma

◦ Leaves the r/w head on the comma after the current string (just to the left of the first symbol of the copy of the current string)

• delete2 – delete 2 (9 states)

◦ Deletes a 2 at the left end of the updated string by changing it to a space and inserting an additional $ after the rightmost $ and shifting to the right until the newly inserted space

◦ Leaves the r/w head on the rightmost symbol of the string to the left of the one just updated

• updateNewString - update new string (5 states, 1 block)

◦ Updates the copy of the current string to be the next string in reverse lexicographic order

◦ Uses delete2 when the length of the new string is less than the current string

◦ Leaves the r/w head on the comma after the new string

• checkDone - check done (17 states)

◦ Compare the new string with Y

▪ If they match, then we are done adding new strings

◦ Leaves the r/w head on the $ at the left end of the input if they match

◦ Leaves the r/w head on the # to the left of the current string if they do not match

• Main program (3 states, 5 blocks)

◦ Uses insertLeftTerminator, insertCurrentStringMarker, copyCurrentString, and checkDone

 

2 of 3 © 2020, Dave Garrison

 

◦ After checkDone returns

▪ If the r/w head is on the $, moves to the right two symbols and halts and accepts

▪ If the r/w head is on the #, replaces the # to the left of the current string with a comma and replaces the comma to the left of the new string with the # to mark it as the current string

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of