import pandas as pd

# Define the Turing machine
blank = '_'  # blank symbol


def run_tm(w: str, max_steps: int = 20_000):
    """
    Simulate the 6‑state TM for L = { a^i b^i c^i | i >= 0 } on input `w`.
    Returns (accept?, steps).
    """
    # Tape as a dict mapping index -> symbol (sparse)
    tape = {i: ch for i, ch in enumerate(w)}
    head = 0
    state = 'q0'
    steps = 0

    def read():
        return tape.get(head, blank)

    def write(ch):
        if ch == blank:
            tape.pop(head, None)
        else:
            tape[head] = ch

    while state not in ('qacc', 'qrej') and steps < max_steps:
        steps += 1
        sym = read()

        # dispatch
        if state == 'q0':
            if   sym == 'a':  write('X'); head += 1; state = 'q1'
            elif sym == 'X':  head += 1                     # stay q0
            elif sym in 'bc': state = 'qrej'
            elif sym == blank: state = 'qacc'
            else: state = 'qrej'

        elif state == 'q1':
            if   sym == 'a':  head += 1
            elif sym == 'X':  head += 1
            elif sym == 'b':  write('X'); head += 1; state = 'q2'
            elif sym in ('c', blank): state = 'qrej'
            else: state = 'qrej'

        elif state == 'q2':
            if   sym == 'b':  head += 1
            elif sym == 'X':  head += 1
            elif sym == 'c':  write('X'); head -= 1; state = 'q3'
            elif sym in ('a', blank): state = 'qrej'
            else: state = 'qrej'

        elif state == 'q3':
            if   sym in ('a', 'b', 'c', 'X'): head -= 1
            elif sym == blank: head += 1; state = 'q0'
            else: state = 'qrej'

        else:  # should never reach
            state = 'qrej'

    return (state == 'qacc', steps if steps < max_steps else None)


tests = [
    "", "abc", "acb", "aabbcc", "aaabbbccc", "aabbbcc", "abcc",
    "bca", "abcabc", "aaaabbbbcccc", "aaabbbcc"
]

results = []
for s in tests:
    accept, steps = run_tm(s)
    results.append({'input': repr(s), 'accepted': accept, 'steps': steps})

df = pd.DataFrame(results)
import ace_tools as tools; tools.display_dataframe_to_user("TM test results", df)