Finite State Machines
A finite state machine has a fixed number of states and no external memory, making it weaker but far easier to analyze than a Turing machine.
The model
A finite state machine (FSM) reads its input one symbol at a time and moves between a finite set of states. Unlike a Turing machine, it has no tape to write on: its entire memory is which state it is in. When the input ends, whether it is in an accepting state decides the answer.
What it can and cannot do
FSMs recognize exactly the regular languages. They can check patterns like "an even number of 1s" or "contains the substring ABBA." They cannot count without bound, so they cannot check that parentheses are balanced to arbitrary depth, which needs unbounded memory.
Deterministic and nondeterministic
A deterministic FSM has one next state per symbol. A nondeterministic FSM may have several, accepting if any path accepts. Remarkably, the two recognize the same languages: any nondeterministic FSM can be converted to a deterministic one, though the state count may grow exponentially.
Why they matter
- Regular expressions compile directly into finite state machines
- Lexical analyzers in compilers are FSMs
- Protocol and hardware controllers are specified as state machines
- They are the base of the Chomsky hierarchy of language classes
The power ladder
FSMs sit at the bottom of a ladder of computational power. Add a stack and you get pushdown automata, which recognize context-free languages. Add an unbounded read-write tape and you get the full power of a Turing machine. Each rung buys more memory discipline and more expressiveness.
A worked idea
To recognize binary strings divisible by 3, use three states for the remainder 0, 1, 2. Each incoming bit doubles the running value and adds the bit, so the state updates by a fixed rule. Ending in the remainder-0 state means the number is divisible by 3, all with just three states and no arithmetic storage.