Construct the Moore Machines that will count occurrences of substring 'ab' over the input ∑ = {a,b} and convert into Mealy Machine.

Step 1: Define the Moore Machine

A Moore machine can be defined as a 6-tuple (Q, ∑, δ, X, Λ, G) where:

• Q is a finite set of states.
• ∑ is a finite input alphabet.
• δ: Q x ∑ → Q is the transition function.
• X is the set of output symbols.
• Λ: Q → X is the output function.
• G is the initial state.

Step 2: Construct the Moore Machine

For the given problem, we need to count occurrences of substring 'ab' over the input ∑ = {a,b}. The Moore machine M can be defined as follows:

• Q = {q0, q1, q2}, where q0 is the initial state.
• ∑ = {a, b}
• δ is defined as:
  • δ(q0, a) = q1
  • δ(q0, b) = q0
  • δ(q1, a) = q1
  • δ(q1, b) = q2
  • δ(q2, a) = q1
  • δ(q2, b) = q0
• X = {0, 1}
• Λ is defined as:
  • Λ(q0) = 0
  • Λ(q1) = 0
  • Λ(q2) = 1

Step 3: Convert the Moore Machine to a Mealy Machine

A Mealy machine can be defined as a 6-tuple (Q, ∑, δ, X, Λ', q0) where:

• Q is a finite set of states.
• ∑ is a finite input alphabet.
• δ: Q x ∑ → Q is the transition function.
• X is the set of output symbols.
• Λ': Q x ∑ → X is the output function.
• q0 is the initial state.

The conversion from a Moore machine to a Mealy machine can be done by changing the output function Λ to Λ' such that for each transition δ(q, a) = p in the Moore machine, we define Λ'(q, a) = Λ(p) in the Mealy machine.

So, the Mealy machine M' equivalent to the Moore machine M is:

• Q = {q0, q1, q2}, where q0 is the initial state.
• ∑ = {a, b}
• δ is the same as in M.
• X = {0, 1}
• Λ' is defined as:
  • Λ'(q0, a) = Λ(q1) = 0
  • Λ'(q0, b) = Λ(q0) = 0
  • Λ'(q1, a) = Λ(q1) = 0
  • Λ'(q1, b) = Λ(q2) = 1
  • Λ'(q2, a) = Λ(q1) = 0
  • Λ'(q2, b) = Λ(q0) = 0

This Mealy machine will count occurrences of substring 'ab' over the input ∑ = {a,b}.