####################################################################### # add_base2.yvtm # # See http://cs.marlboro.edu/courses/spring2011/formal_languages/ # code/machines/base10_add/base10_add.vtm # which does the same thing as this but in base 10. # # Starting tape : X + Y # Ending tape : X + Y = Z # where X, Y, Z are all base two numbers e.g. 11 + 10 = 101 # # The method used here is to loop over add digits pairwise, starting # at the right sides of X and Y, copying the results to Z, # and carrying the 1 to the next pairwise sum as needed. # # Pretty much the way addition is taught in grade school. # # More explicitly it looks like this. # # 1. Move to far right, put down the "=" mark. # # 2. Scan left to find corresponding pairs of digits (or 0 if missing), # change to similar symbol but with "seen" status. # # This first part of the main loop takes place in several pieces : # # i. Find rightmost non-processed digit of Y. # ii. Remember it in state, mark as seen, and continue leftward. # iii. Find rightmost non-processed digit of X. # iv. Remember sum in state, mark as seen. # # 3. Move to right past = to write the sum as a single digit. # Move all previous sum digits to the right one place. # # This is the second part of the main loop. # # To loop back, change state to "scan left" as in step 2; # however, if the sum was > 9, change to a "carry-the-1" state, # which will increment the either Y or X when found. # # I'll use the first few letters for "already processed", # (0 1) => (a, b) # # 4. When no unprocessed X or Y is found, we're done. # Then just translate (a, b) back to (0, 1) # # Each time two digits are added, we must consider the two # cases of when there is or isn't a carry-the-1 from another # operation. Therefore the possible results of one digit addition are # # 0 + 0 no_carry = 0 # 0 + 1 no_carry = 1 # 0 + 1 carry_the_1 = 2 (i.e. 0, carry-the-1) # 1 + 1 carry_the_1 = 3 (i.e. 1, carry-the-1) # # In the processing itself the other situations which # need to be handled include # * no X digit found but Y still remaining, # * no Y digit found but X still reamining, # * "carry-the-1" state but no X or Y # # Here's what this sample calculation looks like. # # $ python yvtm.py add_base2.yvtm # <1> 0 0 1 + 1 1 : Start # 1 <0> 0 1 + 1 1 : Start # 1 0 <0> 1 + 1 1 : Start # 1 0 0 <1> + 1 1 : Start # 1 0 0 1 <+> 1 1 : Start # 1 0 0 1 + <1> 1 : Start # 1 0 0 1 + 1 <1> : Start # 1 0 0 1 + 1 1 <_> : Start # 1 0 0 1 + 1 <1> = : FindY # 1 0 0 1 + <1> b = : Find+_1 # 1 0 0 1 <+> 1 b = : Find+_1 # 1 0 0 <1> + 1 b = : FindX_1 # 1 0 0 b <+> 1 b = : FindAnswer_2 # 1 0 0 b + <1> b = : FindAnswer_2 # 1 0 0 b + 1 = : FindAnswer_2 # 1 0 0 b + 1 b <=> : FindAnswer_2 # 1 0 0 b + 1 b = <_> : WriteAnswer_2 # 1 0 0 b + 1 b <=> 0 : SkipAnswer_carry1 # 1 0 0 b + 1 = 0 : FindY_carry1 # 1 0 0 b + <1> b = 0 : FindY_carry1 # 1 0 0 b <+> b b = 0 : Find+_2 # 1 0 0 + b b = 0 : FindX_2 # 1 0 <0> b + b b = 0 : FindX_2 # 1 0 a + b b = 0 : FindAnswer_2 # 1 0 a b <+> b b = 0 : FindAnswer_2 # 1 0 a b + b = 0 : FindAnswer_2 # 1 0 a b + b = 0 : FindAnswer_2 # 1 0 a b + b b <=> 0 : FindAnswer_2 # 1 0 a b + b b = <0> : WriteAnswer_2 # 1 0 a b + b b = 0 <_> : ShiftAnswer_carry1_0 # 1 0 a b + b b = <0> 0 : SkipAnswer_carry1 # 1 0 a b + b b <=> 0 0 : SkipAnswer_carry1 # 1 0 a b + b = 0 0 : FindY_carry1 # 1 0 a b + b = 0 0 : FindY_carry1 # 1 0 a b <+> b b = 0 0 : FindY_carry1 # 1 0 a + b b = 0 0 : FindX_1 # 1 0 b + b b = 0 0 : FindX_1 # 1 <0> a b + b b = 0 0 : FindX_1 # 1 a b + b b = 0 0 : FindAnswer_1 # 1 a a + b b = 0 0 : FindAnswer_1 # 1 a a b <+> b b = 0 0 : FindAnswer_1 # 1 a a b + b = 0 0 : FindAnswer_1 # 1 a a b + b = 0 0 : FindAnswer_1 # 1 a a b + b b <=> 0 0 : FindAnswer_1 # 1 a a b + b b = <0> 0 : WriteAnswer_1 # 1 a a b + b b = 1 <0> : ShiftAnswer_0 # 1 a a b + b b = 1 0 <_> : ShiftAnswer_0 # 1 a a b + b b = 1 <0> 0 : SkipAnswer # 1 a a b + b b = <1> 0 0 : SkipAnswer # 1 a a b + b b <=> 1 0 0 : SkipAnswer # 1 a a b + b = 1 0 0 : FindY # 1 a a b + b = 1 0 0 : FindY # 1 a a b <+> b b = 1 0 0 : FindY # 1 a a + b b = 1 0 0 : FindX_noY # 1 a b + b b = 1 0 0 : FindX_noY # 1 a b + b b = 1 0 0 : FindX_noY # <1> a a b + b b = 1 0 0 : FindX_noY # b a b + b b = 1 0 0 : FindAnswer_1 # b a b + b b = 1 0 0 : FindAnswer_1 # b a a + b b = 1 0 0 : FindAnswer_1 # b a a b <+> b b = 1 0 0 : FindAnswer_1 # b a a b + b = 1 0 0 : FindAnswer_1 # b a a b + b = 1 0 0 : FindAnswer_1 # b a a b + b b <=> 1 0 0 : FindAnswer_1 # b a a b + b b = <1> 0 0 : WriteAnswer_1 # b a a b + b b = 1 <0> 0 : ShiftAnswer_1 # b a a b + b b = 1 1 <0> : ShiftAnswer_0 # b a a b + b b = 1 1 0 <_> : ShiftAnswer_0 # b a a b + b b = 1 1 <0> 0 : SkipAnswer # b a a b + b b = 1 <1> 0 0 : SkipAnswer # b a a b + b b = <1> 1 0 0 : SkipAnswer # b a a b + b b <=> 1 1 0 0 : SkipAnswer # b a a b + b = 1 1 0 0 : FindY # b a a b + b = 1 1 0 0 : FindY # b a a b <+> b b = 1 1 0 0 : FindY # b a a + b b = 1 1 0 0 : FindX_noY # b a b + b b = 1 1 0 0 : FindX_noY # b a b + b b = 1 1 0 0 : FindX_noY # a a b + b b = 1 1 0 0 : FindX_noY # <_> b a a b + b b = 1 1 0 0 : FindX_noY # _ a a b + b b = 1 1 0 0 : CleanUp # _ 1 a b + b b = 1 1 0 0 : CleanUp # _ 1 0 b + b b = 1 1 0 0 : CleanUp # _ 1 0 0 + b b = 1 1 0 0 : CleanUp # _ 1 0 0 1 <+> b b = 1 1 0 0 : CleanUp # _ 1 0 0 1 + b = 1 1 0 0 : CleanUp # _ 1 0 0 1 + 1 = 1 1 0 0 : CleanUp # _ 1 0 0 1 + 1 1 <=> 1 1 0 0 : CleanUp # _ 1 0 0 1 + 1 1 = <1> 1 0 0 : Done # ** Accept ** # # Jim Mahoney | Oct 10 2016 | MIT License ############################################################# # This sample problem is # 1001 + 11 # which in base 10 9 + 3 = 12 # and so the answer should be # 1001 + 11 = 1100 # without the spaces. tape: "1001+11" start: Start blank: _ accept: [ Done ] reject: [] machine: # From Start, skip past the plus sign ... - [ Start, "+", Start, "+", right ] # ... and all the digits - [ Start, 0, Start, 0, right ] - [ Start, 1, Start, 1, right ] # At the right tape end, write an = and begin the step 2 loop - [ Start, _, FindY, "=", left ] # Skip past any digits in Y already processed, which will be symbols (a,b) # Same for "carry-the-1" rules . - [ FindY, a, FindY, a, left ] - [ FindY_carry1, a, FindY_carry1, a, left ] - [ FindY, b, FindY, b, left ] - [ FindY_carry1, b, FindY_carry1, b, left ] # Rightmost unprocessed Y digit found. # Save it, write the correspoding "seen this digit" symbol, # and keep moving left, looking for X digit next. # Remember y+carry in state. (20 rules) - [ FindY, 0, Find+_0, a, left ] - [ FindY_carry1, 0, Find+_1, a, left ] - [ FindY, 1, Find+_1, b, left ] - [ FindY_carry1, 1, Find+_2, b, left ] # Skip past leftward (0,1) in Y, for any of Find+_* states. - [ Find+_0, 0, Find+_0, 0, left ] - [ Find+_1, 0, Find+_1, 0, left ] - [ Find+_2, 0, Find+_2, 0, left ] - [ Find+_0, 1, Find+_0, 1, left ] - [ Find+_1, 1, Find+_1, 1, left ] - [ Find+_2, 1, Find+_2, 1, left ] # + sign found. Start looking for rightmost unprocessed X digit. - [ Find+_0, "+", FindX_0, "+", left ] - [ Find+_1, "+", FindX_1, "+", left ] - [ Find+_2, "+", FindX_2, "+", left ] # + sign found, no Y digit, no carry : set state to remember that and continue to X. - [ FindY, "+", FindX_noY, "+", left ] # + sign found, no Y digit, carry: treat as y=1. - [ FindY_carry1, "+", FindX_1, "+", left ] # Skip past any digits in X already processed (symbols a,b) for any of the FindX_* states. - [ FindX_0, a, FindX_0, a, left ] - [ FindX_1, a, FindX_1, a, left ] - [ FindX_2, a, FindX_2, a, left ] - [ FindX_0, b, FindX_0, b, left ] - [ FindX_1, b, FindX_1, b, left ] - [ FindX_2, b, FindX_2, b, left ] # Skip past any of 10 digits in X already processed for FindX_noY. - [ FindX_noY, a, FindX_noY, a, left ] - [ FindX_noY, b, FindX_noY, b, left ] # Rightmost X digit found. # Add it to the y+carry saved in state, write corresponding "seen it" symbol, # change to FindAnswer_* state, and start moving right looking for =. - [ FindX_0, 0, FindAnswer_0, a, right ] - [ FindX_1, 0, FindAnswer_1, a, right ] - [ FindX_2, 0, FindAnswer_2, a, right ] - [ FindX_0, 1, FindAnswer_1, b, right ] - [ FindX_1, 1, FindAnswer_2, b, right ] - [ FindX_2, 1, FindAnswer_3, b, right ] # Rightmost X digit found but no Y digit, and no carry. Treat as y=0. - [ FindX_noY, 0, FindAnswer_0, a, right ] - [ FindX_noY, 1, FindAnswer_1, b, right ] # No X digit found, but there is a Y digit or carry. Treat as x=0. - [ FindX_0, _, FindAnswer_0, _, right ] - [ FindX_1, _, FindAnswer_1, _, right ] # No X digit found, no Y digit saved, no carry. # Move right converting letters in X and Y back to digits, and halt at = . - [ FindX_noY, _, CleanUp, _, right ] # Then move past + during CleanUp. - [ CleanUp, "+", CleanUp, "+", right ] # Convert letters to numbers during cleanup. - [ CleanUp, a, CleanUp, 0, right ] - [ CleanUp, b, CleanUp, 1, right ] # Halt when we hit = during cleanup - [ CleanUp, "=", Done, "=", right ] # FindAnswer_n (n=x+y including carry) moves right past digits or letters - [ FindAnswer_0, 0, FindAnswer_0, 0, right ] - [ FindAnswer_0, 1, FindAnswer_0, 1, right ] - [ FindAnswer_0, a, FindAnswer_0, a, right ] - [ FindAnswer_0, b, FindAnswer_0, b, right ] - [ FindAnswer_1, 0, FindAnswer_1, 0, right ] - [ FindAnswer_1, 1, FindAnswer_1, 1, right ] - [ FindAnswer_1, a, FindAnswer_1, a, right ] - [ FindAnswer_1, b, FindAnswer_1, b, right ] - [ FindAnswer_2, 0, FindAnswer_2, 0, right ] - [ FindAnswer_2, 1, FindAnswer_2, 1, right ] - [ FindAnswer_2, a, FindAnswer_2, a, right ] - [ FindAnswer_2, b, FindAnswer_2, b, right ] - [ FindAnswer_3, 0, FindAnswer_3, 0, right ] - [ FindAnswer_3, 1, FindAnswer_3, 1, right ] - [ FindAnswer_3, a, FindAnswer_3, a, right ] - [ FindAnswer_3, b, FindAnswer_3, b, right ] # FindAnswer_n also moves right past + - [ FindAnswer_0, "+", FindAnswer_0, "+", right ] - [ FindAnswer_1, "+", FindAnswer_1, "+", right ] - [ FindAnswer_2, "+", FindAnswer_2, "+", right ] - [ FindAnswer_3, "+", FindAnswer_3, "+", right ] # When Find_Answer_n gets to the = , change state to WriteAnswer_n. - [ FindAnswer_0, "=", WriteAnswer_0, "=", right ] - [ FindAnswer_1, "=", WriteAnswer_1, "=", right ] - [ FindAnswer_2, "=", WriteAnswer_2, "=", right ] - [ FindAnswer_3, "=", WriteAnswer_3, "=", right ] # Now we need to write the new answer digit, # and shift the old answer digits right one place. # The state needs to keep track of two things: # - which answer digit is being shifted, and # - whether there's a carry or not. # For example, if we want to write 3, we treat # that as writing 1 and remembering to carry the 1. # Write the new answer on top of the old; start shifting the old digits. - [ WriteAnswer_0, 0, ShiftAnswer_0, 0, right ] - [ WriteAnswer_0, 1, ShiftAnswer_1, 0, right ] - [ WriteAnswer_1, 0, ShiftAnswer_0, 1, right ] - [ WriteAnswer_1, 1, ShiftAnswer_1, 1, right ] - [ WriteAnswer_2, 0, ShiftAnswer_carry1_0, 0, right ] - [ WriteAnswer_2, 1, ShiftAnswer_carry1_1, 0, right ] - [ WriteAnswer_3, 0, ShiftAnswer_carry1_0, 1, right ] - [ WriteAnswer_3, 1, ShiftAnswer_carry1_1, 1, right ] # If WriteAnswer was on a blank, then change direction right then. - [ WriteAnswer_0, _, SkipAnswer, 0, left ] - [ WriteAnswer_1, _, SkipAnswer, 1, left ] - [ WriteAnswer_2, _, SkipAnswer_carry1, 0, left ] - [ WriteAnswer_3, _, SkipAnswer_carry1, 1, left ] # Continue shifting the remaining old digits. - [ ShiftAnswer_0, 0, ShiftAnswer_0, 0, right ] - [ ShiftAnswer_0, 1, ShiftAnswer_1, 0, right ] - [ ShiftAnswer_1, 0, ShiftAnswer_0, 1, right ] - [ ShiftAnswer_1, 1, ShiftAnswer_1, 1, right ] - [ ShiftAnswer_carry1_0, 0, ShiftAnswer_carry1_0, 0, right ] - [ ShiftAnswer_carry1_0, 1, ShiftAnswer_carry1_1, 0, right ] - [ ShiftAnswer_carry1_1, 0, ShiftAnswer_carry1_0, 1, right ] - [ ShiftAnswer_carry1_1, 1, ShiftAnswer_carry1_1, 1, right ] # Stop shifting when we hit a blank. - [ ShiftAnswer_0, _, SkipAnswer, 0, left ] - [ ShiftAnswer_1, _, SkipAnswer, 1, left ] - [ ShiftAnswer_carry1_0, _, SkipAnswer_carry1, 0, left ] - [ ShiftAnswer_carry1_1, _, SkipAnswer_carry1, 1, left ] # Move left looking for the = - [ SkipAnswer, 0, SkipAnswer, 0, left ] - [ SkipAnswer, 1, SkipAnswer, 1, left ] - [ SkipAnswer_carry1, 0, SkipAnswer_carry1, 0, left ] - [ SkipAnswer_carry1, 1, SkipAnswer_carry1, 1, left ] # When we get to that =, continue the main loop by looking for the next Y digit. - [ SkipAnswer, "=", FindY, "=", left ] - [ SkipAnswer_carry1, "=", FindY_carry1, "=", left ] # ... and that's it. (Whew!)