Reference no: EM133155110

Question: Construct a Turing machine that adds two ternary real numbers. An input will be of the form X#Y, where X and Y are elements of {0, 1, 2}+.{0, 1, 2}+. In particular, X = xnxn-1 ... x1x0.x-1x-2 ... x-k, and Y = ymym-1 ... y1y0.y-1y-2 ... y-l with xi, yi in {0, 1, 2}, X = (xn x 3n) + (xn-1 x 3n-1) + ... + (x1 x 31) + (x0 x 30) + (x-1 x3-1) + ... + (x-k x 3-k), and Y = (ym x 3m) + (ym-1 x 3m-1) + ... + (y1 x 31) + (y0 x 30) + (y-1 x 3-1) + ... + (y-1 x 3- l).

Your Turing machine must be a single tape, one way infinite, deterministic Turing machine. When the Turing machine completes, the tape should contain Z, where Z = X + Y. You do not need to delete X#Y from the tape, you can simply position the Turing machine's read/write head at the beginning of Z (leftmost symbol of Z).

For your result to be correct, it will not have any leading 0s to the left of the decimal point unless Z is less than 1, and the result will not having any trailing 0s to the right of the decimal point, unless Z is an integer. That is, the following are invalid, 02.0 and 2.10, and likewise the following three are valid, 0.2, 1.0, and 0.0. For the trailing 0s, you can move to the right end of Z and move left over 0s, overwriting them with blank spaces, until either a 1, a 2, or a decimal point is found.

If a decimal point is found, the blank space to the right of it can be changed back to a 0. For leading 0s, when you position the read/write head on the leftmost symbol of Z, you can simply move to the right of any leading 0s until either a 1, a 2, or a decimal point is found. If a decimal point is found, simply move left. For this assignment you may want to use blocks (subroutines in JFLAP) to build your Turing machine. You can also make use of the S directive for read/write head motion (L - left, R- right, S - stay). 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).

Your Turing machine cannot make use of the blank spaces to the left of the input string. 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 the blank space in block file names). When you create a block, I would suggest you create it as a separate file, test it, and then insert it into your main program (or a block that goes into your main program). I've heard from students that if you are editing a block from within your main program and you save the block before closing it, it will overwrite your file with the block you are editing (you need to exit block edit mode prior to saving). Keep backup copies of all of your file (often). You can do a save as while editing a block to save the block as a separate file.

It took me about three hours to implement my version of the program, an hour to test/debug it, and probably an hour to write a Java program to verify the output was correct (unfortunately Java's BigDecimal class doesn't support non-base 10 representations). For my final test I generated 1000 random strings of the form X#Y where X and Y have length between 4 and 10 symbols and ran my program against the strings and verified that the result of adding X and Y was correct.

Below is some additional information about my implementation.

My Turing machine uses 4 blocks. The blocks perform the following actions.
• InsertLeftTerminatorAndAppendDollarSign - block that inserts a "tiny_mce_markerquot; at the left end of the input, shifting all of the input to the right one position, and appends a "#" at the right end of the string
- The block has 9 states and rewinds the tape leaving the read/write head under the "tiny_mce_markerquot;
- The "#" appended to the input is to mark where Z (Z = X + Y) begins
• fixOrder - block that reorders X & Y if X has less symbols to the right of the decimal point than does

? The block has 24 states
? After this block completes we have the first of the two strings has at least as many symbols to the right of the decimal point as the second - this is to make it more efficient to pad the second of the two with 0s such that they have the same number of symbols to the right of the decimal point
• fixLength - block that appends 0s to the end of Y to make X & Y have the same number of digits to the right of the decimal point
? The block has 12 states
• performAddition - block that actually adds X & Y
? The block has 46 states
? We will discuss performing ternary addition in class
• main program - uses the four blocks and one accept state

My Turing machine uses an input alphabet of {0, 1, 2, ., #} and a tape alphabet of {0, 1, 2, ., x, a, b, c, #, $, blank space}. The x is used to mark symbols of X and Y as having been processed and a, b, and c are used to mark 0, 1, and 2 when they need to be restored in the future (in fixOrder & fixLength).

I also did a verion of the program without using blocks. Assuming I counted correctly, it has 85 states. Below is an image of the version of my program that uses blocks (no real help there).

Below is an image of the version of my program that doesn't use blocks. All of the transitions have been replaced with a single transition. The image is to show the same structure works without blocks.

Attachment:- Programming assignment.rar