Finite State Machines and What They Recognise
A machine with a fixed set of states that moves between them as it reads one input symbol at a time, drawn as a state transition diagram or written as a table. It has no memory beyond the state it is in, which fixes what it can and cannot recognise.
What a learner can do afterwards
- Draw a state transition diagram for a simple device and give the matching table
- Decide whether a given input string is accepted by a machine
- Say why counting unlimited nested brackets is beyond any fixed set of states
1 · Read
A finite state machine has a fixed set of states, an alphabet of input symbols, and rules for moving between states. It reads one input symbol at a time and jumps along its arrows, with no other memory at all. Its whole memory is the current state: everything older is forgotten.
Here is a machine that accepts binary strings ending in 01. It has three states: A for start, B for just saw a 0, and C for just saw 01, which accepts. From A, 0 goes to B and 1 stays at A. From B, 0 stays at B and 1 goes to C. From C, 0 goes back to B and 1 goes back to A. Feed it 1, 0, 1 and you walk A to A to B to C, so 101 is accepted. Feed it 1, 1, 0 and you end at B, so 110 is rejected.
A state diagram of circles and arrows says the same thing as a transition table, so practise converting both ways. Acceptance is a precise claim: start in the start state, consume each symbol exactly once, and check whether you finish in an accepting state. There is no peeking ahead and no second pass.
That fixed memory draws a sharp line around what the machine can recognise. Counting unlimited nested brackets needs counting without limit, but the states are fixed and finite, so brackets fall beyond the line. Turnstiles, vending slots, and simple text matchers all live inside it and share the same ceiling.
Fixed states, one symbol at a time, and the landing state decides.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.