Finite State Machines (FSMs) are powerful tools in computational theory, and interpreting their diagrams is essential to understanding how they process input strings.
What are state transition diagrams?
State transition diagrams are visual representations used to describe the behaviour of FSMs in response to a series of input symbols. They show how an FSM moves from one state to another, step by step, when given an input string. These diagrams consist of various components that are essential to understanding how the machine behaves.
Each state in the diagram is represented by a circle, with arrows (called transitions) showing the path from one state to another when a specific input symbol is read. The start state is usually marked with an incoming arrow that originates from nowhere (it points at the start state but does not come from another state), and accepting states are drawn as double circles to distinguish them.
FSMs discussed here do not produce output symbols; instead, their function is to accept or reject strings based on whether the machine ends in an accepting state after reading the entire input.
Practice Questions
FAQ
In the context of deterministic finite state machines (FSMs), which are the only type examined at A-Level, each state must have exactly one transition for each input symbol. If a diagram includes more than one arrow from the same state for the same symbol, it cannot be a valid deterministic FSM. You should treat this as a diagram error or misinterpretation. Often, this happens when transitions are drawn unclearly or overlapping, especially in hand-drawn or printed examples. Check to see if the diagram uses shorthand where multiple symbols (like 0,1) appear on a single arrow, which indicates that both inputs follow the same transition. In exam conditions, if you’re given a diagram with ambiguous or conflicting transitions, state that a deterministic FSM must have only one transition per input per state and explain how this inconsistency makes the machine undefined for that input symbol. Always seek clarification or apply the principle of determinism if needed.
No. A string is only accepted by a finite state machine if after the final input symbol is read, the FSM is in an accepting state. It does not matter how many accepting states were passed through during the string’s processing. FSMs do not retain memory of previous states beyond the current one—they are memoryless beyond state. Therefore, it is the final state alone that determines acceptance. For example, a string might lead the FSM into an accepting state mid-way, but if subsequent input causes it to transition into a non-accepting state, the entire string is rejected. This principle is crucial and often tested in FSM interpretation tasks. Always ensure that you follow the full input and only check acceptance after the last symbol has been processed. Tracing the path and writing down each state change helps avoid this common misconception.
If a string includes a symbol that is not part of the input alphabet defined for the FSM, the string is automatically rejected. FSMs can only process symbols they recognise. For instance, if the FSM is defined over the binary alphabet {0, 1}, and the input string contains a 2, a, or any other character, there will be no valid transition from any state for that symbol. The machine halts, and the input is not accepted. This kind of error is often overlooked, especially in longer strings or unfamiliar alphabets. When practising or sitting an exam, carefully check that each symbol in the string is part of the machine’s defined input set. If not, you can immediately conclude that the string is rejected without needing to trace any transitions. In design or exam scenarios, always clearly define the FSM’s input alphabet and verify that input strings comply with it.
Such FSMs are called partial FSMs. In a partial FSM, certain states may lack transitions for one or more input symbols. If, during simulation, the FSM reaches a state and the next input symbol has no defined transition, the machine halts immediately and the string is rejected. This is not an error—it’s a valid design technique often used to simplify FSMs that only recognise a narrow pattern or language. You should be vigilant when simulating such machines. As soon as you hit a symbol that lacks a corresponding transition from the current state, you must conclude that the machine cannot proceed and therefore the string is not accepted. Some FSMs instead use a trap state (also called a dead state) to handle undefined inputs—any illegal input sends the FSM into this state, which loops on all symbols and is never accepting. Whether a partial FSM halts or a trap state is used, the result is the same: rejection.
The most reliable method is to write down the state after processing each input symbol in the order they appear in the string. This helps track the FSM's path step-by-step and avoid losing your place, especially in diagrams with multiple transitions or looping states. A good format is to list the input symbol followed by the state you enter after reading it. You can use arrows or a table-style format to keep it organised. Additionally, physically marking the transitions you follow on the diagram—by drawing arrows or circling states—can help reduce errors. After the entire input is read, check the final state and compare it with the FSM’s list of accepting states. If time permits, retrace the simulation in reverse to ensure consistency. This disciplined approach minimises the chance of skipping transitions, misreading symbols, or ending in the wrong state, all of which are common mistakes in exam settings.
