FSM Simulator
Build finite state machines by adding states and transitions, then test input strings to see whether they are accepted or rejected. Includes step-by-step trace of the computation. Matches AQA A Level CS (7517) specification §4.4.2.
📖 Learn Step-by-StepDFA over {0,1} that accepts strings with an even number of 1s (including zero 1s).
Click the canvas to add a state. Click a state to select it, then use the controls below.
Use the Add Transition button to connect two states. Symbols are auto-added to the alphabet.
Transitions:
Test a String
Finite State Machine Practice Questions
A DFA over {0,1} has states S0 (start, accepting) and S1. Transitions: δ(S0,0)=S0, δ(S0,1)=S1, δ(S1,0)=S1, δ(S1,1)=S0. How many of these strings are accepted: 0, 1, 10, 11, 010, 101, 111, 1001?
A DFA has 3 states. How many transitions are needed at minimum for a complete DFA over an alphabet of size 2?
An FSM has states {A, B, C}. State A is the start state. States B and C are accepting. If the input string '010' ends in state A, is it accepted? Enter 1 for yes, 0 for no.
A DFA recognises the language of binary strings divisible by 3. The minimum number of states required is?
A DFA over {a,b} accepts all strings containing the substring 'aba'. What is the minimum number of states required?
Quick reference — Finite State Machines
What is an FSM?
A finite state machine (FSM) is an abstract model of computation with a finite number of states. It reads an input string symbol-by-symbol, transitioning between states according to a transition function. If it finishes in an accepting state, the string is accepted.
DFA vs NFA
A DFA (Deterministic Finite Automaton) has exactly one transition per state/symbol pair. An NFA (Non-deterministic Finite Automaton) can have multiple transitions for the same symbol, or ε-transitions. Both recognise the same class of languages (regular languages).
Formal definition
A DFA is a 5-tuple (Q, Σ, δ, q₀, F) where Q is a finite set of states, Σ is the input alphabet, δ is the transition function δ : Q × Σ → Q, q₀ is the start state, and F ⊆ Q is the set of accepting (final) states.
Regular languages
The set of languages recognised by FSMs is exactly the set of regular languages. These are the same languages that can be described by regular expressions.
AQA exam tips
- Always label the start state with an arrow
- Use double circles for accepting states
- Ensure your DFA is complete — every state must have a transition for every symbol
- Trace through test strings step by step to verify your machine