Question

Construct a Moore machine for a binary input sequence such that if it has a substring '110', the machine outputs A; if it has a substring ‘101', the machine outputs B, otherwise machine outputs C.

Answer 1

The Moore machine diagram and state transition table as described below.

Answer 2

The Moore machine is designed with states representing the longest suffix of the input that is a prefix of either '110' or '101', or the patterns themselves. Each state has a fixed output.

• Q0, Q1, Q10, Q11 are intermediate states that haven't completed a target pattern yet, so they output 'C'.
• QA is reached when '110' is detected as the suffix, and it outputs 'A'.
• QB is reached when '101' is detected as the suffix, and it outputs 'B'.

Transitions from QA and QB are crucial for handling subsequent inputs and potential new patterns:

• From QA (Output A):
  • If input is '0' (e.g., '...1100'): The longest suffix that is a prefix of '110' or '101' is '0'. Thus, it transitions to Q0 (Output C). The machine stops outputting 'A' because '110' is no longer the suffix.
  • If input is '1' (e.g., '...1101'): The suffix is '101'. This completes the '101' pattern. Thus, it transitions to QB (Output B).
• From QB (Output B):
  • If input is '0' (e.g., '...1010'): The longest relevant suffix is '0'. It transitions to Q0 (Output C).
  • If input is '1' (e.g., '...1011'): The suffix is '011', and the longest relevant prefix is '11'. It transitions to Q11 (Output C).

This design ensures that the machine's output dynamically reflects the current suffix's match to the patterns, prioritizing the pattern that is the immediate suffix.