ITPEC FE Morning April 2018 Question 4
Which of the following bit strings is accepted by the automaton described in the state transition diagram below? Here, each string is processed one bit at a time in sequence from the left.
Explanation
1010 — the only string that reaches the double-circled state, which needs a 1 followed later by a 0.
Reading the diagram: the initial (left) state stays on 0 and moves to the middle state on 1; the middle state stays on 1 and moves to the accepting (right) state on 0; the accepting state stays there on 0 or 1. So a string is accepted once a 0 follows a 1.
- •
1010: left, 1 to middle, 0 to accepting, then 1 and 0 stay there: accepted - •
0000: every 0 loops on the initial state: rejected - •
0111: 0 stays on the initial state, the first 1 moves to the middle state, the other 1s loop there: rejected - •
1111: the first 1 moves to the middle state and the rest loop there: rejected
Answer (c)
Why not others:
- •(a) 0000 — contains no 1, so it never leaves the initial state
- •(b) 0111 — ends in the middle state: no 0 comes after the first 1
- •(d) 1111 — also ends in the middle state; only a 0 leads from there to the accepting state
Key rule: Trace an automaton one symbol at a time and judge only the state you end in: the string is accepted when that final state is an accepting (double-circled) 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.