--- title: "Finite State Machines and What They Recognise" description: "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 " canonical: https://lightmysky.com/learn/computing/finite-state-machines-and-what-they-recognise-mt_gIk7tQ229w source: https://lightmysky.com/learn/computing/finite-state-machines-and-what-they-recognise-mt_gIk7tQ229w.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Computing · Area: Algorithms & Data Structures · Ages 17 to 18 Page: https://lightmysky.com/learn/computing/finite-state-machines-and-what-they-recognise-mt_gIk7tQ229w ## Ready when they can - 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 ## Lesson: Little machines that remember one thing 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. **Example.** 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. **Tip.** 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. **Recap.** Fixed states, one symbol at a time, and the landing state decides. ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Logic Circuits That Add and Remember](https://lightmysky.com/learn/computing/logic-circuits-that-add-and-remember-mt_zPgkt6zf-i) ## Opens up - [Lexing and Parsing: From Text to a Syntax Tree](https://lightmysky.com/learn/computing/lexing-and-parsing-from-text-to-a-syntax-tree-mt_-ZlCxZ3SOh) - [Turing Machines and the Universal Machine](https://lightmysky.com/learn/computing/turing-machines-and-the-universal-machine-mt_vS_QC1tCSM)