A finite-state machine (FSA) models a simple machine with finitely many states and inputs. Each input moves it to a state determined by its current state and that input. section 5.3
A vending machine illustrates the idea: its response to a selection button depends on the input and its current state, such as whether payment is sufficient and the item is available. section 5.3
A trie can be viewed as an FSA: nodes are states, edge labels are inputs, and the root is the start state. Nodes marked as success states recognize accepted strings; the set of those strings is the machine’s language. section 5.3
This view makes trie optimization a state-minimization problem: merge functionally identical states while preserving the language accepted. Tries store word prefixes; minimizing them can reduce redundant states and memory use. section 5.3 section 5.6
