Finite State Machines and What They Recognise · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Little machines that remember one thing

Computing · Algorithms & Data Structures · ages 17-18
Name ______________________   Date ____________

  1. What is the whole memory of a finite state machine?

    • Every symbol it ever read
    • Only its current state
    • The full dictionary

  2. What three parts define a finite state machine?

    • States, input symbols, and movement rules
    • Wires, batteries, and light bulbs
    • Stories, pictures, and songs

  3. A state diagram and a transition table can say the same thing.

    Circle one:   True   False

  4. Run 110 through the lesson machine. Is it accepted?

    • No, because it ends at B
    • Yes, because it contains a 1
    • Yes, because it starts with 1

  5. Run 101 through the lesson machine. Where do you finish?

    • At B, so it is rejected
    • At A, so it is rejected
    • At C, so it is accepted

  6. From state C, reading a 0 sends the lesson machine back to B.

    Circle one:   True   False

  7. What must a machine for strings ending in 01 remember?

    • The whole string from the start
    • Only the last two symbols
    • The number of machines built

  8. Why can no fixed-state machine match unlimited nested brackets?

    • Brackets are too round to read
    • Machines dislike punctuation
    • It would need to count without limit, but states are fixed
LightMySky · lightmysky.comW1-mt_gIk7tQ229w-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Little machines that remember one thing W1-mt_gIk7tQ229w-s1

  1. Only its current state · History beyond the current state is forgotten.
  2. States, input symbols, and movement rules · States plus symbols plus rules are the complete machine.
  3. True · Circles with arrows and rows with entries carry identical information.
  4. No, because it ends at B · The walk ends at B, which does not accept.
  5. At C, so it is accepted · A to A to B to C lands in the accepting state.
  6. True · A trailing 0 means the machine just saw a 0, which is state B.
  7. Only the last two symbols · The tail decides, and three states hold exactly that much.
  8. It would need to count without limit, but states are fixed · Open brackets pile up without bound, and finite states cannot track the pile.
Worksheet · LightMySky