--- 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-11-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 - Represent a deterministic string recogniser as a state transition diagram and matching table - Decide whether a given input string is accepted by a machine - Explain why recognising balanced parentheses at arbitrary nesting depth needs more than finitely many states ## Lesson: Little machines that remember one thing Here we use a deterministic finite-state recogniser. It has finitely many states, an input alphabet, transition rules, a start state and accepting states. Each combination of a state and an input symbol determines one next state. It reads one symbol at a time. Its current state is all its working memory. That state can summarise earlier input without storing the whole history. **Example.** To recognise binary strings ending in 01, start in A. B means the current string ends in 0. C means it ends in 01; only C accepts. A covers all other cases, including empty input. The rows below give the next state for input 0 and input 1. These are three suffix categories, not a record of every possible pair of final symbols. *(drawing: For 1001, apply one transition per symbol. The final C accepts.)* Draw each state as a circle and each transition as an arrow labelled with its input. Mark the start with an incoming arrow and accepting states with double circles. An arrow from A to B labelled 0 becomes the table entry: current state A, input 0, next state B. Record every transition and preserve the start and accepting states. To test a string, read all symbols before checking acceptance. Empty input leaves the machine at its start state. Balanced parentheses have matching openings and closings, with no early closing. A machine with n states reads the n+1 prefixes containing zero through n openings. Two different depths must reach the same state. Add enough closings to balance the shallower depth. The deeper one stays unbalanced, but both runs now follow identical transitions from the same state. They cannot get different acceptance decisions. No fixed finite set of states handles every nesting depth. **Recap.** Fixed states, one symbol at a time, and the landing state decides. *Lesson, questions and flashcards on finite-state recognisers written for this dataset.* ## 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)