a finite-state machine

Picture a subway turnstile. Right now it is locked. You push a coin in and it becomes unlocked; you walk through and it locks again. The turnstile does not remember how many people walked through yesterday, or how many coins it has ever taken. At every instant the whole of what it knows is captured by one word: locked or unlocked. That single word is its state, and a machine whose entire memory is one such state, chosen from a fixed finite list, is a finite-state machine.

More precisely, a finite-state machine reads its input one symbol at a time, left to right, and after each symbol it sits in exactly one of finitely many states. The only thing carried from one symbol to the next is which state you are in; there is no scratch pad, no counter, no extra storage on the side. A rule (the transition) says, for the current state and the symbol just read, which state to move to. A traffic light (green to yellow to red to green) and a vending machine that tracks how much money has been inserted are everyday finite-state machines.

The phrase finite-state is the heart of the matter and also its honest limitation. Because there are only finitely many states, the machine can remember only a bounded amount of information no matter how long the input gets. It can remember the last symbol seen, or whether the count so far is even or odd, or which of three coins it is waiting for, but it cannot remember an arbitrarily large running total. That boundary is exactly what makes finite-state machines simple enough to analyse completely, and it is also why they cannot, for example, check that brackets are balanced to any depth.