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 working memory does this recogniser carry between input symbols?

    • The full input history in a separate growing list
    • Its current state, which can summarise earlier input
    • An unlimited count held separately from the current state

  2. Which list defines the deterministic string recogniser used here?

    • States, alphabet, transitions, start state and accepting states
    • States, alphabet, transitions, stored input history and an unlimited stack
    • States, alphabet, stored input history, accepting states and a clock speed

  3. A state diagram and a transition table can describe the same recogniser.

    Circle one:   True   False

  4. A binary recogniser starts at A; only C accepts. On 0, every state goes to B. On 1: A goes to A, B to C, C to A. Does it accept 010?

    • No; its final state is B
    • Yes; visiting C once is enough
    • Yes; containing 01 is enough

  5. A binary recogniser starts at A; only C accepts. On 0, every state goes to B. On 1: A goes to A, B to C, C to A. Run 01101. Where do you finish?

    • At B, a non-accepting state
    • At A, a non-accepting state
    • At C, the accepting state

  6. A binary recogniser uses B exactly for strings ending in 0 and C exactly for strings ending in 01. Reading a symbol appends it. From C, reading 0 sends it to B.

    Circle one:   True   False

  7. Start at A. On 0, every state goes to B. On 1: A goes to A, B to C, C to A. Both 0 and 110 finish in B. What shared fact does B record?

    • The complete strings have equal lengths and identical symbols
    • The current string ends in 0
    • The complete strings contain equal numbers of zeros and ones

  8. Why can no finite-state recogniser accept exactly the balanced-parentheses strings at every nesting depth?

    • Every closing parenthesis must be rejected, even when matching openings came before it
    • Every nesting depth needs a different input alphabet, so one alphabet cannot cover all depths
    • Two opening depths share a state, so an identical closing suffix cannot distinguish them
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. Its current state, which can summarise earlier input · The current state is the entire working memory. It can preserve selected facts about earlier symbols.
  2. States, alphabet, transitions, start state and accepting states · Transitions specify moves. The start state begins the run; accepting states decide acceptance after the input ends.
  3. True · Every labelled arrow can become a current-state, input and next-state entry. Start and accepting states must also agree.
  4. No; its final state is B · 010 visits C but finishes at B. Acceptance depends on the final state.
  5. At C, the accepting state · The trace is A, B, C, A, B, C. The final C accepts.
  6. True · Appending 0 makes the string end in 0, the category represented by B.
  7. The current string ends in 0 · Every 0 leads to B, and no 1 does. Since the start state is A, the recogniser finishes in B exactly when the string ends in 0.
  8. Two opening depths share a state, so an identical closing suffix cannot distinguish them · Two depths reach the same state. Closing the shallower depth balances only that string, but the recogniser must make the same decision for both.
Worksheet · LightMySky