ITPEC FE Morning April 2018 Question 4

Finite State Automaton (FSA) — String Acceptance — determining which input string reaches an accepting state.

The automaton has three states: S0 (initial), S1, and S2 (accepting, shown with a double circle).

Transitions:
- S0 on 0 → S0 (loop), on 1 → S1
- S1 on 1 → S1 (loop), on 0 → S2
- S2 on 0 or 1 → S2 (loop — once reached, stays accepting)

To reach S2, the input must contain the substring 10 (a 1 moves to S1, then a 0 moves to S2). After reaching S2, all remaining input keeps the automaton in S2.

Tracing each option:
- 1010: S0 →1→ S1 →0→ S2 →1→ S2 →0→ S2 → accepted
- 0000: S0 →0→ S0 →0→ S0 →0→ S0 →0→ S0 → never leaves S0
- 0111: S0 →0→ S0 →1→ S1 →1→ S1 →1→ S1 → stuck in S1
- 1111: S0 →1→ S1 →1→ S1 →1→ S1 →1→ S1 → stuck in S1

Why not others:
- (a) 0000 — all zeros loop in S0; never transitions toward S2
- (b) 0111 — reaches S1 but never encounters a 0 afterward to move to S2
- (d) 1111 — same issue as (b); stays in S1 with no 0 to trigger the S1→S2 transition

Key rule: trace each input symbol one at a time through the state machine; the string is accepted only if the final state is an accepting state (double circle).

AI-generated — may contain errors