Machine Input1-Tape Binary IncrementImportExportTapesStart StateBlank SymbolTape 1 InputRuleProduction RulesFormat: state,read -> next,write,movesMoves: `l`, `r`, `s`# Add 1 to a binary number written on the tape (LSB on the right). # Scan to the rightmost bit, then propagate the carry leftward. # # q0 – scan right to find the end # q1 – propagate carry leftward # qf – done q0,0 -> q0,0,r q0,1 -> q0,1,r q0,B -> q1,B,l q1,1 -> q1,0,l q1,0 -> qf,1,s q1,B -> qf,1,s
