don v2.0

I built this crazy machine in JFLAP that takes 2 binary inputs and 1 operator. (Obviously this was an assignment, who would do this on their free time?) And good lord it looks ugly. It has about 100 states, zig-zagging around like a grape vine. The more I think about what I am doing, the more confusing it gets. It is best to approach this like a robot with tunnel vision. Break it down to parts, build what you need one-by-one, and put it all together. At least that's how I did it.

Here are the specs of the assignment:

• 2 binary numbers seperated by an operator. No leading 0's unless it is a 0. So each binary number is in the language: (0 + 1(0+1)*)
• Operators are: +,*, or =. + adds the 2 numbers, * multiplies to two, and = checks if it is equal. If equal, the output is 1, else it returns 0. X will be the output for any invalid input, like 1001*10+1 (2 operators) or 0101+11 (leading 0) or 11* (empty binary).

The input will be in the format of: M+N, M*N, M=N, M being the first number and N the second. The tape head always starts at the left-most position.

Addition:
Pretty easy and straight forward. Approach it like you would on paper, from right to left and carry when needed. But you need 2 dummy variables as space holders to increment the column you need to add to. X = 0 and Y = 1.

1. Get right most digit of N.
2. If 0, mark it X. Else, mark it Y.
3. Travel left to right-most digit of M
4. If 0 (or blank), mark it with same char from N. And then move right to the right-most digit of N, which is 1 left of the X or Y.
5. If it was 1, mark it with the appropriate letter (1+1=0=X or 1+0=1=Y). Carry the 1 by moving left until the first 0 or blank. While traveling, mark each 1's with 0's (not X) and the 0 (that we are searching for) mark it 1
6. Repeat 1-5 until N has no more digits left.

Confusing? Yeah, it is probably easier to understand by example.

So 11101(29)+110(6) = 100011(35)

Multiplication:
Seems hard at first, but not that much harder than addition. Hell, I didn't even know how to multiple binary numbers. You have to approach it in an addition way, the old fashioned way. ie: 5*4 = 5+5 = 10 + 5 = 15 + 5 = 20. So you do exactly that in binary but obviously there are plenty more steps involved. So we need to keep track of the updated total as well as the original value that gets added to itself. So something like this: M*N@M. @ being the seperator between N and a copy of M, which is P.

1. Append a copy of M after N, include a seperator.
2. Subtract 1 from N, if not 0 then continue. If 0 then we are done.
3. Add P to M.
4. Repeat 2-3 until the N = 0.
To come to think of it, it is not that hard afterall.

It may look something like this (I'll show the changes after writes since each step would take forever):

So it is not that much more difficult than the addition, but just a little more sophisticated and requires more attention to detail.

Equality:
Probably the easiest and shortest one. Start from the left-most of M and compare it to the left-most of N. If true, then continue. Else, then it is not equal. Use X,Y variables for M and T for N for matches. F isn't really needed because once it is not equal, it fails.

Here is what my Turing Machine ended up looking like. Yes it is ugly, but (imo) very readable. Top section was the validation, then addition, muliplication, then equality.

Told you it was ugly. But it works 100%