Building a Tokenizer from Scratch

FSM Parser Theory. A friendly conversation with Claude Opus Q: automata theory have a class hierarchy, starting from combinational logic. right? Yes, that's a clean way to frame it. The hierarchy goes from "no memory" to "more memory": Combinational logic — output depends only on current input. No memory, no state. Just pure boolean functions ( AND , OR , etc.). Finite State Machine (FSM) — adds memory in the form of state . Output depends on current input + current state. Memory is finite and fixed. Pushdown Automaton (PDA) — FSM + a stack . The stack gives it unlimited but structured memory (LIFO). This is what recognizes nested structures like matching parentheses. Turing Machine — FSM + an infinite tape (read/write). The most powerful model; can simulate any computation. Each level can recognize a strictly larger class of languages (the Chomsky hierarchy): Machine Language class Example Combinational — Boolean expression FSM Regular /ab*c/ PDA Context-free Balanced {}[]() Turing Re