ITPEC FE Subject A October 2025 Question 4
For an automaton with input and output symbols {0, 1} and a state transition diagram shown below, which of the following is the output string for the input string 0011001110? Here, S1 represents the initial state, and the label x/y on each arc indicates that if x is an input, then y is the corresponding output at the state transition.
Explanation
0001000110 — trace the input one symbol at a time; the arc taken gives both the output and the next state.
Arcs in the diagram:
Trace of 0011001110 from S1:
Answer (a)
Why not others:
- •(b) 0001001110 — stays in S3 on the 0s at steps 5 and 6, so step 7 outputs 1; the 0/0 arc from S3 returns to S1, where a 1 outputs 0
- •(c) 0010001000 — outputs 1 at step 3, but that 1 is read in S1, whose arc is 1/0; it also outputs 0 at steps 4, 8 and 9, where the 1/1 arcs apply
- •(d) 0011111110 — outputs 1 at steps 5 and 6, whose inputs are 0, yet every 0 arc in the diagram outputs 0
Key rule: In an automaton labelled x/y, the output belongs to the arc: for each symbol, find the arc leaving the current state with that input, write its output, then move to the arc's target state.
Basic Theory · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.