A state is the circuit's memory, boiled down to what matters. A combinational circuit only sees its inputs right now. A sequential circuit also carries a state, held in flip-flops, which sums up the past.
The key idea is summary. A machine doesn't store its whole input history, only the part that can still affect what it does:
- A turnstile needs two states: Locked or Unlocked.
- A machine that spots two 0s in a row needs three: "no 0 yet", "one 0" and "two or more 0s".
- A machine that tracks the number of 1s mod 3 needs three: remainder 0, 1 or 2, however long the input is.
The state the machine is in now is the present state. At each active clock edge it moves to the next state, chosen by the present state and the inputs. In a state diagram each state is a circle; in a state table each is a row.
When you design a finite state machine, start by writing in words what each state remembers. If two states would remember the same thing, they're probably equivalent states.