Loading...
4.4.2.1Theory of ComputationCore
Finite State and Mealy Machines
A finite state machine stores a finite summary of its input history. Trace one transition for each input symbol and distinguish acceptance from output production.
What you'll be able to do
- Interpret state diagrams and transition tables
- Trace an accepting FSM
- Trace transition-labelled outputs in a Mealy machine
1
Define an accepting machine
An FSM has a finite set of states, an input alphabet and rules for transitions. An accepting machine also identifies its start and accepting states. To test a string, begin at the start state and consume its symbols in order; acceptance depends on the final state after all input is consumed.
A machine recognising binary strings ending in 1 can use states Last0 and Last1, starting in non-accepting Last0. Any 0 leads to Last0 and any 1 leads to accepting Last1. Passing through an accepting state partway through does not guarantee final acceptance.
2
Add outputs on transitions
In a Mealy machine, an output is associated with a transition, commonly labelled input/output. Read the current state and input together to determine both the next state and emitted output. AQA assesses Mealy machines rather than requiring recall of every transducer variant.
For running parity, states Even and Odd summarise how many 1s have appeared modulo two. Input 0 leaves the state unchanged; input 1 toggles it. If a transition emits the new parity, outputs are 0 for Even and 1 for Odd. This is an output task, separate from accepting a complete string.
3
Check the machine’s coverage
A deterministic table must give an unambiguous transition for each allowed state/input pair under the chosen model. Missing or competing transitions need clarification. Mark the start state and acceptance notation distinctly so they are not confused with ordinary edges.
An FSM can distinguish a fixed finite number of histories but cannot retain an unbounded counter. It can track parity indefinitely because only two summaries are needed. This finite-memory limitation helps explain which languages are regular and why some matching tasks need a richer model.
| Current parity | Input | Next parity | Output |
|---|---|---|---|
| Even | 0 | Even | 0 |
| Even | 1 | Odd | 1 |
| Odd | 0 | Odd | 1 |
| Odd | 1 | Even | 0 |
4
Work through the problem
Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.
Example 1Does the ends-in-1 machine accept 1010?
1The successive states are Last1, Last0, Last1, Last0.
2The final state is non-accepting.
AnswerNo, even though accepting states were visited earlier.
Example 2Trace the parity Mealy machine on 101.
11 changes Even to Odd and emits 1.
20 stays Odd and emits 1; the final 1 changes to Even and emits 0.
AnswerOutput 110; final state Even.
Common mistakes to avoid
Accepting as soon as an accepting state is reached.
Consume the whole input first.
Reading a Mealy output as an input label.
Use the stated input/output convention.
Key takeaways
- States summarise relevant history.
- Acceptors and output machines answer different questions.
- Finite state memory limits the recognised behaviour.
Test yourself
Answer a few questions, then review anything you missed.
Next step
Browse practice topicsKeep practising
Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.