Adopt a Machine

The shelter below has five honest machines looking for a home. Each knows exactly one trick — one sorting job from the conveyor-belt game in Notes 02. You adopt one, and adoption comes with three responsibilities.

1. Draw it. Circles, arrows, start arrow, double circle on the yes-states — the picture from Notes 02. Paper or any drawing tool; a phone photo is fine.
2. Type it. Write your machine as the Notes 02 dictionary, with the ten-line runner underneath. The full pattern is in §03 — adopting is mostly editing six lines of it.
3. Run it. Feed it six strings — three that should get a YES, three that should get a NO — and print the verdicts.

Name your machine. The first line of your file introduces it, like: # This is Gerald. Gerald says YES when the string ends in b. Fair warning, and this is the whole game: I will feed Gerald strings he has never seen. Gerald has to actually work — not just on your six.

Five machines, five jobs — each doable with the tools from Notes 02 and nothing else. The state counts are a promise, not a demand: if your design works, it works. Before wiring any arrows, ask the Notes 02 design question — what is the least my machine must remember? — and give every state a plain-words name: "even so far," "mid-chime," "ruined forever."

Here is a complete, working adoption file for a machine that is not in the shelter — the Gatekeeper, who says YES when the string starts with a. It's exactly the dictionary and runner from Notes 02, plus the six verdicts. Copy it, then make it yours: new name at the top, new states and rules in the dictionary, your own six strings at the bottom.

# This is the Gatekeeper. It says YES when the string starts with a.
# States: S = "nothing read yet", Y = "started with a — happy forever",
#         N = "started with b — a trap: no way back".

GATEKEEPER = {
    "alphabet": {"a", "b"},
    "states":   {"S", "Y", "N"},
    "start":    "S",
    "accept":   {"Y"},
    "delta": {                        # the rule table, box for box
        "S": {"a": "Y", "b": "N"},
        "Y": {"a": "Y", "b": "Y"},
        "N": {"a": "N", "b": "N"},
    },
}

def run_dfa(m, w):
    # Walk machine m over string w. One pass, no peeking ahead.
    state = m["start"]
    for ch in w:
        if ch not in m["alphabet"]:
            raise ValueError(f"{ch!r} is not one of this machine's letters")
        state = m["delta"][state][ch]
    return state in m["accept"]

# Three strings that should be YES, three that should be NO.
for w in ["a", "ab", "abba", "", "b", "ba"]:
    verdict = "YES" if run_dfa(GATEKEEPER, w) else "NO"
    print(f"{w!r:>8}  ->  {verdict}")

Run it and you get three YES lines and three NO lines. Notice the empty string "" is one of the six — the Gatekeeper hasn't seen an a, so it's a NO. Test the empty string whenever it makes an interesting test for your job.

One rule about the runner: run_dfa must stay general — it walks whatever rule table it's handed, and the job lives entirely in the data. A file that answers the six strings with if statements is not a machine, it's a parrot, and parrots fail the surprise strings.

To be explicit about what I do not want: no report, no PDF, no written argument, no test framework, no extra features. Two attachments. Late work loses 10% per day, as in the syllabus. Stuck for more than twenty minutes on any step, email me: yair.chaya@liu.edu.

Five checkboxes, 20 points each. I go down this exact list, so grade yourself before you submit — check all five and you've earned your 100.

That last box is the one students miss. The Waltz Counter should face a long string and the empty one; the Doorbell should face a chime in the middle. Pick strings a skeptic would pick.