Invent a Tiny Language

# Project 2 -- Invent a Tiny Language.
# Fill in the YOUR PART box, run the file, screenshot everything it prints.
# The starter below is the Laughing Language (ha, haha, hahaha, ...). It runs
# out of the box so you can see a finished run — then replace it with yours.

from collections import deque

# ============================ YOUR PART ============================

GRAMMAR = {
    "S": [["h", "a", "S"], ["h", "a"]],    # S -> haS | ha
}
START = "S"

GOOD = ["ha", "haha", "hahaha", "hahahaha", "hahahahaha"]  # five YES strings
BAD  = ["", "h", "ah", "hah", "ahah"]                      # five NO strings

# ========================= END OF YOUR PART ========================
# Everything below is straight from Notes 06 and 07. Don't edit it.

def generate(grammar, start, max_len):
    """Every string the grammar builds, up to max_len, shortest first."""
    found, seen = set(), set()
    queue = deque([(start,)])
    while queue:
        form = queue.popleft()
        if form in seen:
            continue
        seen.add(form)
        if sum(1 for s in form if s not in grammar) > max_len:
            continue                         # already too long
        spots = [i for i, s in enumerate(form) if s in grammar]
        if not spots:
            found.add("".join(form))         # no variables left: a real string
            continue
        i = spots[0]                         # leftmost variable
        for rule in grammar[form[i]]:
            queue.append(form[:i] + tuple(rule) + form[i + 1:])
    return sorted(found, key=lambda w: (len(w), w))

def accepts(pda, w, max_stack=50):
    """Try every world (state, position, stack), breadth-first."""
    start = (pda["start"], 0, "")
    queue, seen = deque([start]), {start}
    while queue:
        state, pos, stack = queue.popleft()
        if pos == len(w) and state in pda["accept"]:
            return True                          # some world made it
        for frm, read, pop, push, to in pda["moves"]:
            if frm != state:
                continue
            if read and (pos == len(w) or w[pos] != read):
                continue                         # wrong input symbol
            if pop and not stack.endswith(pop):
                continue                         # wrong top of stack
            new_stack = stack[:len(stack) - len(pop)] + push[::-1]
            if len(new_stack) > max_stack:
                continue                         # guard against endless pushing
            world = (to, pos + len(read), new_stack)
            if world not in seen:
                seen.add(world)
                queue.append(world)
    return False                                 # every world died

def grammar_to_pda(grammar, start):
    """Expand-and-match PDA for a grammar with one-character symbols."""
    moves = [("s", "", "", start + "$", "L")]    # start variable on top of $
    terminals = set()
    for var, rules in grammar.items():
        for rule in rules:
            moves.append(("L", "", var, "".join(rule), "L"))   # top is a variable: guess a rule
            terminals.update(s for s in rule if s not in grammar)
    for t in sorted(terminals):
        moves.append(("L", t, t, "", "L"))       # top is a terminal: match the input
    moves.append(("L", "", "$", "", "f"))        # marker on top: every prediction came true
    return {"start": "s", "accept": {"f"}, "moves": moves}

# ------------- the script does the rest: don't touch -------------

print()
print("=" * 52)
print("  YOUR LANGUAGE SPEAKS -- the first strings it builds")
print("=" * 52)
for w in generate(GRAMMAR, START, 10)[:15]:
    print("   " + (w if w else "(the empty string)"))

print()
print("=" * 52)
print("  THE CHECKER -- your grammar, running as a machine")
print("=" * 52)
checker = grammar_to_pda(GRAMMAR, START)
wrong = []
for w, want in [(g, True) for g in GOOD] + [(b, False) for b in BAD]:
    got = accepts(checker, w)
    shown = w if w else "(the empty string)"
    if got != want:
        wrong.append(shown)
    want_s = "YES" if want else "NO"
    got_s = "YES" if got else "NO"
    mark = "ok" if got == want else "<-- WRONG"
    print(f"   {shown:<20} want {want_s:<4} got {got_s:<4} {mark}")

print()
if len(GOOD) != 5 or len(BAD) != 5:
    print("   Hold on: you need exactly five good and five bad strings.")
elif not wrong:
    print("   ALL 10 CORRECT -- LANGUAGE CERTIFIED")
else:
    print("   Not certified yet. Look again at: " + ", ".join(wrong))
print()