IPA FE Subject A sample Question 4
A question IPA Japan published in 基本情報技術者試験 科目A サンプル問題 問4, translated into English. ITPEC is based on the same exams.
Same question on ITPEC: Oct 2025 Q4 +1 more
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 the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.