ITPEC FE Morning October 2021 Question 6

Finite State Machine (Mealy Machine) — trace the output for a given input string.

Input: 0011001110, start at S1.

Transition table:

• •S1 + 0 → S1, output 0
• •S1 + 1 → S2, output 0
• •S2 + 0 → S1, output 0
• •S2 + 1 → S3, output 1
• •S3 + 0 → S1, output 0
• •S3 + 1 → S3, output 1

Step-by-step trace:

• •0 → S1→S1, out 0
• •0 → S1→S1, out 0
• •1 → S1→S2, out 0
• •1 → S2→S3, out 1
• •0 → S3→S1, out 0
• •0 → S1→S1, out 0
• •1 → S1→S2, out 0
• •1 → S2→S3, out 1
• •1 → S3→S3, out 1
• •0 → S3→S1, out 0

Output: 0001000110 → (a)

Why not others:
- (b) 0001001110 — wrong output at step 7 (S1→S2 outputs 0, not 1)
- (c) 0010001000 — wrong output at step 4 (S2→S3 outputs 1, not 0)
- (d) 0011111110 — treats input as output directly, ignoring transitions

Key rule: In a Mealy machine, output depends on both current state and input. Read x/y as "on input x, output y." Trace each step carefully.

AI-generated — may contain errors