mmn11-q1.yaml

name: binary increment1
source code: |
  # Adds 1 to a binary number.
  input: '00000000000000000000000000000000' # 32 - reject
  blank: ' '
  start state: q0
  table:
    # scan to the rightmost digit
    q0:
      0    : {write: ' ', R: q1}
      ' ': {R: q_reject}

    q1:
      0: {R: q2}
      ' ': {R: q_accept}

    q2:
      0: {R: q3}
      ' ': {L: q4}

    q3:
      0: {R: q2}
      ' ': {R: q_reject}
      
    q4:
      0: {write: ' ', L: q5}
      
    q5:
      0: L
      ['x', ' ']: {R: q6}
      
    q6:
      ' ': {L: q7}
      0: {write: 'x', R: q3}

    q7:
      'x': {write: 0, L}
      ' ': {R: q1}

    q_accept:
    
    q_reject:


  # Exercises:

  # • Modify the machine to always halt on the leftmost digit
  #   (regardless of the number's length).
  #   Hint: add a state between carry and done.

  # • Make a machine that adds 2 instead of 1.
  #   Hint: 2 is '10' in binary, so the last digit is unaffected.
  #   Alternative hint: chain together two copies of the machine from
  #   the first exercise (renaming the states of the second copy).

  # • Make a machine to subtract 1.
  #   To simplify things, assume the input is always greater than 0.
positions:
  q0: {x: 50.51, y: 244.38}
  q1: {x: 223.75, y: 249.16}
  q2: {x: 350.94, y: 250.88}
  q3: {x: 346.6, y: 393.72}
  q4: {x: 494.75, y: 249.41}
  q5: {x: 605.98, y: 249.98}
  q6: {x: 780, y: 242.83}
  q7: {x: 601.01, y: 81.64}
  q_accept: {x: 229.64, y: 47.65}
  q_reject: {x: 170.87, y: 394.54}